# Gossiping

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

×

Problem Loading...

Note Loading...

Set Loading...