Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.independent

Topic: cotpi 62 - Efficient gossiping
Replies: 1   Last Post: Sep 19, 2012 8:40 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View  
James Waldby

Posts: 348
Registered: 1/27/11
Re: cotpi 62 - Efficient gossiping
Posted: Sep 19, 2012 8:40 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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 (2n-2) calls everybody knows each piece of
> gossip - #1 calls #2 calls #3 ... calls #n so #n knows everything
> (n-1) calls, then #n calls #n-1 ... calls #2 calls #1 so everybody
> knows everything (another n - 1 calls).


Another (2n-2) call protocol is for n-1 people to telephone to
person #1, who then calls n-1 people and reveals all.

> And 2n-2 calls are necessary: After n-1 phone calls, there is at least
> one person X who hasn't made any calls. Therefore after n-1 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 n-1 calls until
> each person knows that item x.






--
jiw



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.