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?

Simple, what's not mentioned or hinted at is if Person A can ask Person B "Have you heard the rumor about Waldo yet?" Thus if they answer "No." then Person A can tell Person B, if they have heard it then Person A clearly doesn't need to repeat it to Person B.

To Conclude,

The probability of everyone but Waldo finding out is 100%.

Posted by chris on 2004-12-16 18:03:28