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?

(In reply to Scratching my Head by owl)

I already found a couple of errors (I promised myself I would go sleep, but this is a nagging me.) I needed to update the has-beens (R) before updating the newly-told (II). I also needed to lower the possible people that can be told by the rumor. The first person you speak to can be anyone but yourself and your own teller; the second person you to whom you speak must also exclude the first person, regardless if that person already knew.

I think I am on the right track, as I am now curiously close to twice what Charlie is getting.

Module[{Success,S,II,R,INew,k,loopytimes=1000000},
Do[
   Success=49;II=1;R=0;
   While[II>0,
      INew=0;
      Do[
         If[Random[Integer,{1,S+INew+II+R-2}]£S,
            S=S-1;INew=INew+1,];
         If[Random[Integer,{1,S+INew+II+R-2-1}]£S,
            S=S-1;INew=INew+1,],
      {II}];
      R=R+II; II=INew;
   ];
   If[S==0,Success=Success+1,],
   {k,1,loopytimes}];
Success]

Edited on December 6, 2004, 3:51 am

Edited on December 7, 2004, 3:57 am

Posted by owl on 2004-12-06 03:50:38