All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Monkey Business (Posted on 2004-04-30) Difficulty: 4 of 5
Suppose someone comes onto the site and is bored. That person starts spreading the rumor that levik is a monkey at exactly noon (on day 1) by sending an e-mail to one random person.

Then, each person sends an e-mail about this rumor (at exactly noon, on day 2) to one person. They can send it to anyone on perplexus (but themselves), even if that person already knows the rumor, or even if it was the person who told them about it.

Each successive day at noon, everyone that knows about the rumor sends a message to one other random person.

On average, on what day will everyone know about the rumor if there are 40 people (including the one that spread the rumor initially) at perplexus while the rumor is still spreading?

What if there were x people at perplexus while the rumor is still spreading?

No Solution Yet Submitted by Gamer    
Rating: 3.5000 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
A simpler but flawed way | Comment 8 of 11 |

On the theory that the expected time to reach 40 is equal to the expected time to go from 1 to 2 plus the expected time to go from 2 to 3, plus ... plus the expected time to go from 39 to 40, one could argue that:

When r people already know the rumor, any given person's phoning has probability (40-r)/39 of expanding the knower pool by 1.  That makes the expected number of phone calls it will take to be 39/(40-r).  As there are r calls made during a day, the expected number of days would be 39/((40-r)*r). You'd just add up these values for r = 1 to 39.

The flaw in this logic is its lack of treatment of days as more than just a number of phone calls.  That is, as soon as a new knower is found, the number increases not only for the purpose of decreasing the likelihood of finding a new knower, but also in expanding the number of callers, even though in fact the number of callers does not change until a day boundary arrives.

As a result this calculation arrives at lower expected numbers of days (shown for various values of n in addition to just 40):

 2             1
 3             2
 4             2.75
 5             3.333333
 6             3.805556
 7             4.2
 8             4.5375
 9             4.831746
 10            5.092143
 20            6.740705
 30            7.659197
 40            8.29441
 50            8.779243
 60            9.170968
 70            9.49943
 80            9.782133
 90            10.03022
 100           10.25121
 110           10.45041
 120           10.63173
 130           10.79809
 140           10.95177
 150           11.09457
 160           11.22791
 170           11.35296
 180           11.4707
 190           11.58193
 200           11.68733

While this is probably simple enough to do with pencil and paper, the computer is easier, so the above was produced with:

FOR n = 2 TO 9
 GOSUB calcIt
FOR n = 10 TO 200 STEP 10
 GOSUB calcIt
days = 0
FOR r = 1 TO n - 1
 days = days + (n - 1) / ((n - r) * r)
PRINT n, days

  Posted by Charlie on 2004-05-01 10:13:00
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (5)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information