Jump to content
BrainDen.com - Brain Teasers
  • 0

A bug problem


BMAD
 Share

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.

Link to comment
Share on other sites

8 answers to this question

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

 

.

 

Link to comment
Share on other sites

  • 0

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;
}

Link to comment
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 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.

Link to comment
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.

 

 

 

Link to comment
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

Edited by marksadams01
typo
Link to comment
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.

 

 

Happy Bug equation.JPG

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

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

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

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...