Jump to content
BrainDen.com - Brain Teasers
  • 0
BMAD

A bug problem

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.

Share this post


Link to post
Share on other sites

8 answers to this question

  • 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 this post


Link to post
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;
}

Share this post


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

Share this post


Link to post
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 this post


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

 

 

Happy Bug equation.JPG

  • Upvote 1

Share this post


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

Share this post


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

Share this post


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

 

 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


  • Recently Browsing   0 members

    No registered users viewing this page.

×