Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: cotpi 62  Efficient gossiping
Posted:
Sep 19, 2012 8:40 PM


On Wed, 19 Sep 2012 14:29:27 0700, christian.bau wrote: > On Sep 19, 5:58 pm, cotpi <puzz...@cotpi.com> wrote: >> Each of n male citizens knows a different piece of gossip. They >> are allowed to exchange the gossip they know by phone. During a >> call, just one of the men speaks and tells the other all the >> gossip he knows. What is the minimum number of calls required to >> enable each man to know all the gossip? > > It is possible that after (2n2) calls everybody knows each piece of > gossip  #1 calls #2 calls #3 ... calls #n so #n knows everything > (n1) calls, then #n calls #n1 ... calls #2 calls #1 so everybody > knows everything (another n  1 calls).
Another (2n2) call protocol is for n1 people to telephone to person #1, who then calls n1 people and reveals all.
> And 2n2 calls are necessary: After n1 phone calls, there is at least > one person X who hasn't made any calls. Therefore after n1 phone > calls there is at least one item of information x that is only known > to one person. With every further phone call, at most one person can > learn the item of information x, so it takes another n1 calls until > each person knows that item x.
 jiw



