Assume we have $n \ge 4$ people which everyone of them got a news. In every two steps these people call each other and transfer their all news they know. Prove that these people can know all the news in $2n-4$ calls.
Asked
Active
Viewed 291 times
1
-
4This is known as the Gossip Problem. The proof is surprisingly lengthy...references can be found in the link (or online). – lulu Feb 24 '17 at 12:50
-
Related: Gossip problem proof by induction – CiaPan Feb 24 '17 at 13:01
1 Answers
1
For the $(n+1)$-st person $N$ it's enough to make one call to person $A$ to communicate the $N$'s news to $A$, then let the whole $n$-people group communicate all news to each other in $G(n)$ calls and finally to make another $A$ to $N$ talk to communicate all news to $N$.
I'm sure you can find the number of talks $G(n+1)$ now, related to $G(n)$.
CiaPan
- 13,049
-
This only shows that $G(n+1)≤G(n)+2$. It is also easy to prove that $G(n+1)≥G(n)+1$ so either $G(n+1)=G(n)+1$ or $G(n)+2$. Alas, $G(4)=G(3)+1$ so it really isn't obvious that the correct answer is (usually) $+2$. – lulu Feb 24 '17 at 13:30