2nd Towns Spring 1981 Problem 4 n people each have a unique item of news. Every hour on the hour phone calls take place between pairs of people. Each phone call lasts exactly an hour and the two participants exchange the news they have at the end of the call. How long does it take for everyone to know all the news?
A simple induction shows that after m rounds, no one knows more than 2 m items of news. So if n = 2 m , we need at least m rounds. Another induction shows that m rounds is sufficient for n = 2 m , for if it is true for m, then for m+1 we must use the arrangement for m simultaneously for the first 2 m and second 2 m people and then in the final round everyone in one group calls someone in the other group. Suppose 2 m  k these cover between them all the news. 2nd Towns Spring 1981© John Scholes jscholes@kalva.demon.co.uk 15 Nov 2003 Last corrected/updated 15 Nov 03