Gossiping

Probability Level 5

A popular formulation assumes there are $n$ people, each one of whom knows a scandal which is not known to any of the others. They communicate by telephone, and whenever two people place a call, they pass on to each other as many scandals as they know. What is the minimum number of calls needed before all $n$ people know about all the scandals?

Denoting the scandal-spreaders as $A, B, C$ , and $D$ , a solution for $n=4$ is given by $\{A,B\}, \{C,D\}, \{A,C\}, \{B,D\}$ . The $n=4$ solution can then be generalized to $n > 4$ by adding the pair $\{A,E\}$ to the beginning and end of the previous solution, i.e. $\{A,E\}, \{A,B\}, \{C,D\}, \{A,C\}, \{B,D\}, \{A,E\}$ .

Let $f(n)$ be the number of minimum calls necessary to complete gossiping among $n$ people, where any pair of people may call each other. Then $f(1)=0, f(2)=1, f(3)=3.$

Find

$f(20)$ if two-way communication is possible $($ and denote this number by $A);$
$f(20)$ if only one-way communication is possible, e.g. where communication is done by letters or telegrams $($ and denote this number by $B).$

Find $A + B$ .

The answer is 74.

1 solution

Geoff Pilling
Dec 25, 2016

For two way communication, you can use the strategy Vijay describes above, which gives the number of calls as:

$f_{2way}(n) = 2n -4$ for $n > 3$

For one way communication, for 2 people you need 2 calls (A calls B and B calls A) And when you introduce a new caller you need 2 additional calls, i.e. C calls A at the beginning and then A calls C at the end. So in general,

$f_{1way}(n) = 2n -2$ for $n > 1$

So,

$f_{2way}(20) = 36$

$f_{1way}(20) = 38$

$36+38 = \boxed{74}$

Gossiping

The answer is 74.

1 solution

0 pending reports