(famous) Gossips

AvovA · January 14th, 2010, 11:10 pm

Here is a very famous puzzle:There are n ladies, and each of them knows some item of gossip not known to theothers. They communicate by telephone, and whenever one lady calls another, they tell each other all that they know at that time. How many calls are required before each lady knows everything?

wileysw · January 14th, 2010, 11:40 pm

this is also discussed here before: here and herei don't know an easy proof of the conclusion, but the answer is 2n-4.----- ----- ----- ----- -----couple of references:baker & shostak, discrete mathematics, 2:191-193, 1972hurkens, nieuw archief voor wiskunde 5/1(2):208-210, 2000

DJAverage · January 14th, 2010, 11:48 pm

Haven't noticed the previous post.

AvovA · January 15th, 2010, 12:59 am

By the way, here is a collection of several solutions:http://www.mathematik.uni-bielefeld.de/ ... ossips.pdf

raags · January 15th, 2010, 4:46 am

How can it be 2n-4? Suppose there are just 2 ladies (n=2), then it will take only one call and each of them will know everything...but for n=2 (2n-4 =0) i.e. # of calls will be zero. Am I missing something here?QuoteOriginally posted by: wileyswthis is also discussed here before: here and herei don't know an easy proof of the conclusion, but the answer is 2n-4.----- ----- ----- ----- -----couple of references:baker & shostak, discrete mathematics, 2:191-193, 1972hurkens, nieuw archief voor wiskunde 5/1(2):208-210, 2000

wileysw · January 15th, 2010, 5:56 am

raags, you are absolutely right. my post was sloppy. 2n-4 only holds for n>=4. when n=2, it's 1 as you said, and n=3 results 3. you could check with the references above for details.