A bug problem

[BMAD]

For a particular bug population, a bug is either classified as happy, sad, or neutral.

For each generation,

all happy bugs birth 1 sad and 1 neutral bug.

all sad bugs birth 2 happy bugs

all neutral bugs birth one happy bug and one sad bug

all birthing bugs die after birthing.  No bug lives more than one generation and birth at the same time.  These bugs do not require mating to reproduce.

The initial generation only consists of one happy bug.

Write an explicit function to determine for the nth generation how many happy bugs there are.

[dgreening]

A friend and I were working on this. Mark came up with an elegant solution.

Close-form (explicit function) solution:

 

Spoiler

 

Define  as the number of Happy Bugs in Generation g, where initial conditions, .  Then,

 

 

For                  þ

 

For                  þ

 

For            þ

 

For            þ

 

For            þ

 

For       þ

 

For       þ

 

 

Etc

 

.

 

[sushma]

int no_of_happy_bug(int gen) {

        int happy = 1;
        int sad = 0;
        int neutral = 0;
        int generation = 1;

    while (generation <= gen) {
        int h = 0;
        int s = 0;
        int n = 0;
        if (happy >= 1) {
            s = s + happy;
            n = n + happy;
        }

        if (sad >= 1) {
            h = h + (2 * sad);

        }

        if (neutral >= 1) {
            h = h + neutral;
            s = s + neutral;
        }

        happy = h;
        sad = s;
        neutral = n;
        generation++;
    }
    return happy;
}

[BMAD]

On 7/21/2017 at 9:59 AM, sushma said:

int no_of_happy_bug(int gen) {

        int happy = 1;
        int sad = 0;
        int neutral = 0;
        int generation = 1;

    while (generation <= gen) {
        int h = 0;
        int s = 0;
        int n = 0;
        if (happy >= 1) {
            s = s + happy;
            n = n + happy;
        }

        if (sad >= 1) {
            h = h + (2 * sad);

        }

        if (neutral >= 1) {
            h = h + neutral;
            s = s + neutral;
        }

        happy = h;
        sad = s;
        neutral = n;
        generation++;
    }
    return happy;
}

by explicit, I was referring to a function that for any mth generation you can generate the h, s, and n without the need to recursively derive the list.

[phil1882]

lets do several steps and see if we can develop such a function.

1 H

1 S 1 N

3 H 1 S

2 H 3 S 3 N

9 H 5 S 2 N

12 H 11 S 9 N

31 H 21 S 12 N

54 H 43 S 31 N

 

so here are our rules.

H_n = 2*S_n-1 +N_n-1

S_n = H_n-1 +N_n-1

N_n = H_n-1

so, combining  we have...

S_n = N_n +N_n-1

then

S_n-1 = N_n-1 +N_n-2

thus

H_n = 2*(H_n-2 +H_n-3) +H_n-2

H_{n =} 3*H_n-2 +2*H_n-3

so...

F(x) = 1  +3x^2 +2x^3 +9x^4 +12x^5 ...

3x^2*F(x) =  +3x^2           +9x^4  +6x^5

2x^3*F(x) =            +2x^3           +6x^5

F(x)*(1 -3x^2 -2x^3) = 1

F(x) =1/(1 -3x^2 -2x^3)

thus it will be the nth term of this series, whatever that is.

 

 

 

[dgreening]

Sorry, something got lost in copying and pasting. The site does not like the formatting used in word, so I am attaching a picture of the solution ... apologies in advance.

 

 

[marksadams01]

Spoiler

Continues above discussion.

We can explore this function more closely.  Note that the limit of [H_g / P_g] (where P_g is defined as total population of all bugs in generation g) as g approaches infinity is

(1/9)(2^(g+2))/(2^g) = 4/9

 

A quick spreadsheet calculation will show that  [H_g / P_g] does indeed converge to 0.444444444......

    msa

Edited July 27, 2017 by marksadams01
typo

[marksadams01]

6 hours ago, dgreening said:

Sorry, something got lost in copying and pasting. The site does not like the formatting used in word, so I am attaching a picture of the solution ... apologies in advance.

 

 

Oops, and sorry, the subscript for H in the last line should be "6."  Blame my new bifocals.

[Dred]

Spoiler

• happy=4/9*2^n+(5/9+1/3*n)*(-1)^n where at n=0 happy =1, sad=0, neutral=0  Sorry I do not know how to hide the answer.
  Spoiler

   

   

Spoiler