Spreading news: Prove $2n-4$ by induction.

294 Views Asked by At

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.

1

There are 1 best solutions below

1
On

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)$.