Each of $A$, $B$, $C$, $D$, $E$, and $F$ knows a piece of gossip. They communicate by telephone via a central switchboard, which can connect only two of them at a time. During a conversation, each side tells the other everything he or she knows at that point. Determine the minimum number of calls for everyone to know all six pieces of gossip.
Problem
Source: Turkey TST 1999 - P5
Tags: combinatorics proposed, combinatorics
02.07.2012 21:16
This is well-known; the answer is 9. 9 is sufficient: A calls each other person in turn. After 5 calls, A knows all gossips. The last person called by A, WLOG B, also knows all gossips as A told him in the last call. Afterwards, A calls each of C,D,E,F again, now telling everything. 9 is necessary: After $n$ calls, each person can know at most $n+1$ gossips, and there are at most two who knows $n+1$ gossips. Hence it takes 5 calls to get all 6 gossips known by one person. If the first person (WLOG A) to know all gossips is by time $t$, then before that, no one knows all gossips. A must have talked by someone (WLOG B) to obtain his last gossips, hence only A and B know all gossips at time $t$, hence $t \ge 5$. Now, every call could tell at most one other person about all gossips. Hence it rakes another 4 calls to tell C,D,E,F, for a toral of minimum 9 calls.
02.07.2012 22:21
Indeed it is well-known - it's the "gossiping dons" problem, featured among other places in [Béla Bollobás - The Art of Mathematics]. Unfortunately, not well-known enough for you to remember the exact answer, which is $2n-4$ calls for $n\geq 4$ dons, which in this case, for $n=6$, gives the answer as being $2\cdot 6 - 4 = 8$.
03.07.2012 00:53
And a complete solution is here: https://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=440525&p=2484593&hilit=gossiping#p2484593
03.07.2012 03:51
I remembered that the answer was probably 8, but I couldn't find a proof and it seems my argument for 9 has no flaw. Apparently it must have some flaw because it's incorrect.
03.07.2012 05:31
It's this sentence: chaotic_iak wrote: Now, every call could tell at most one other person about all gossips. Consider just the four-person version with calls AB, CD, AC, BD; on the 4th call, two people learn everything, a feat you declared impossible.
27.01.2024 19:15
Working link: https://artofproblemsolving.com/community/c6h440525