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