1st Centromerican 1999 Problem A1 A, B, C, D, E each has a unique piece of news. They make a series of phone calls to each other. In each call, the caller tells the other party all the news he knows, but is not told anything by the other party. What is the minimum number of calls needed for all five people to know all five items of news? What is the minimum for n people?
8, eg BA, CA, DA, EA, AB, AC, AD, AE. 2n-2 Solution Consider the case of n people. Let N be the smallest number of calls such that after they have been made at least one person knows all the news. Then N ≥ n-1, because each of the other n-1 people must make at least one call, otherwise no one but them knows their news. After N calls only one person can know all the news, because otherwise at least one person would have known all the news before the Nth call and N would not be minimal. So at least a further n-1 calls are needed, one to each of the other n-1 people. So at least 2n-2 calls are needed in all. But 2n-2 is easily achieved. First everyone else calls X, then X calls everyone else. 1st OMCC 1999 © John Scholes jscholes@kalva.demon.co.uk 26 November 2003 Last corrected/updated 26 Nov 03