3rd CaMO 1971 Problem 10 n people each have exactly one unique secret. How many phone calls are needed so that each person knows all n secrets? You should assume that in each phone call the caller tells the other person every secret he knows, but learns nothing from the person he calls.
Everyone must receive a call after n-2 calls have been made. For calls up to and including the (n-2)th can communicate in total at most n-2 secrets, which is less than the n-1 which each person needs to receive. Thus the minimum number of calls is 2n-2. This can be achieved as follows. Let the people be A 1 , A 2 , ... , A n . A 1 calls A 2 , then A 2 calls A 3 , and so on up to A n-1 calls A n . After that call A n knows all the secrets. He then calls everyone else. 3rd CaMO 1971 © John Scholes jscholes@kalva.demon.co.uk 10 June 2002