BrainDen.com - Brain Teasers

## Question

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.

## Recommended Posts

• 0

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

.

##### Share on other sites

• 0

int no_of_happy_bug(int gen) {

int happy = 1;
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;
}

h = h + (2 * sad);

}

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

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

##### Share on other sites

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

int no_of_happy_bug(int gen) {

int happy = 1;
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;
}

h = h + (2 * sad);

}

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

happy = h;
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.

##### Share on other sites

• 0

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.

Hn = 2*Sn-1 +Nn-1

Sn = Hn-1 +Nn-1

Nn = Hn-1

so, combining  we have...

Sn = Nn +Nn-1

then

Sn-1 = Nn-1 +Nn-2

thus

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

Hn = 3*Hn-2 +2*Hn-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.

##### Share on other sites

• 0

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.

• 1
##### Share on other sites

• 0
Spoiler

Continues above discussion.

We can explore this function more closely.  Note that the limit of [Hg / Pg] (where Pg 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  [Hg / Pg] does indeed converge to 0.444444444...... msa

typo
##### Share on other sites

• 0
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.

##### Share on other sites

• 0
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

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account. ×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.