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

 Rumor Mill (Posted on 2004-12-03)
Waldo is having a party and has 50 guests, among whom is his brother Basil.

Basil starts a rumor about Waldo; a person hearing this rumor for the first time will then tell another person chosen uniformly at random the rumor, with the exceptions that no one will tell the rumor to Waldo or to the person they heard it from.

If a person who already knows the rumor hears it again, they will not tell it again.

What's the probability that everyone, except Waldo, will hear the rumor before it stops propagating?

What if each person told two people chosen uniformly at random?

 No Solution Yet Submitted by SilverKnight Rating: 4.0000 (6 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Part 2 simulation | Comment 2 of 13 |

The following program simulates one million trials of this experiment:

RANDOMIZE TIMER
FOR trial = 1 TO 1000000
REDIM person(50)
REDIM who(50)
person(1) = 1: p1Ct = 1: p2Ct = 0
DO
FOR i = 1 TO 50
IF person(i) = 1 THEN
DO
r = INT(RND(1) * 50 + 1)
LOOP UNTIL r <> i AND r <> who(i)
DO
s = INT(RND(1) * 50 + 1)
LOOP UNTIL s <> i AND s <> who(i) AND s <> r
IF person(r) = 0 THEN
person(r) = 1
p1Ct = p1Ct + 1
who(r) = i
END IF
IF person(s) = 0 THEN
person(s) = 1
p1Ct = p1Ct + 1
who(s) = i
END IF
person(i) = 2
p2Ct = p2Ct + 1
p1Ct = p1Ct - 1
END IF
NEXT
LOOP UNTIL p1Ct = 0
IF p2Ct = 50 THEN suc = suc + 1
tot = tot + 1
IF trial MOD 100 = 0 THEN
PRINT suc, tot
END IF
NEXT

Out of one million trials on a particular run, in 402 cases the rumor propagated to all 50 guests. That indicates a probability of .000402 or 1 in 2488, but the small number of hits precludes such precision. The expected number of hits per million might be off by 20 or so, so the best that might be said is around .0004 or 1 in 2500.

 Posted by Charlie on 2004-12-03 16:22:19
Please log in:
 Login: Password: Remember me: Sign up! | Forgot password

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

Chatterbox:
Copyright © 2002 - 2019 by Animus Pactum Consulting. All rights reserved. Privacy Information