In: Advanced Math
Suppose that there are n people in a group, each aware of a different secret no one else in the group knows about. These people communicate by phone; when two people in the group talk, they share information about all secretes each knows about. For example, on the first call, two people share information, so by the end of the call, each of them knows about two secretes. The gossip problem asks for the number of phone calls that are needed for all n people to learn about all the secrets.
(a) Find the smallest number of telephone calls when there are 3 and 4 people respectively. [2 marks]
(b) Prove by induction that the total number of phone calls for all n people to learn about all secretes is not more than 2n−4 for any n ≥ 4.
Please feel free to ask any doubts regarding the solution and please rate positively.
Kind Regards.