2nd Irish 1989 Problem B2 Each of n people has a unique piece of information. They wish to share the information. A person may pass another person a message containing all the pieces of information that he has. What is the smallest number of messages that must be passed so that each person ends up with all n pieces of information. For example, if A, B, C start by knowing a, b, c respectively. Then four messages suffice: A passes a to B; B passes a and b to C; C passes a, b and c to A; C passes a, b, c to B.
2(n-1) Solution Let N be the smallest integer such that after N messages at least one person has all the information. Suppose that person is X. Initially X lacks the information from n-1 other people, so each of those people must pass their information to someone (not necessarily X) before X can get it. Hence N ≥ n-1. After N messages, X must be the only person who has all the information (or N would not be minimal). So each of the other n-1 people must receive at least one message. In other words, at least another n-1 messages are required. So we need at least 2(n-1) messages in total. But that also suffices: if the people are A 1 , A 2 , ... , A n , then A 1 passes to A 2 , A 2 to A 3 , ... , A n-1 to A n , then A n to A 1 , A n to A 2 , ... , A n to A n-1 . 2nd Irish 1989 © John Scholes jscholes@kalva.demon.co.uk 20 Oct 2003 Last updated/corrected 20 Oct 03