1971 Canadian MO Problems/Problem 10
Problem
Suppose that people each know exactly one piece of information, and all pieces are different. Every time person phones person , tells everything that knows, while tells nothing. What is the minimum number of phone calls between pairs of people needed for everyone to know everything? Prove your answer is a minimum.
Solution
If all the n people know one distinct thing each, we can, without loss of generality, label them . One way that is always possible is as follows: 1. Starting at , each calls , giving all his information, until we reach , who now knows everything. 2. Starting at , each calls , thus making know everything as well. This requires telephone calls, since make calls on step 1 and make calls on step 2. Now we will show that no more efficient way is possible. We first look at step 1. For some person to know everything, all the others must have made a telephone call at one time, or their information would be unknown. Thus, calls are needed for some person to know everything. We now examine step 2. If only one knows everything, calls must be made, because each of the others must be informed by someone. Thus, calls are needed for everyone to know everything once someone does. Since each telephone call can only inform 1 person, there is no way to make more than one person know everything first, so only one does, and the solution holds. We showed earlier that this is possible, so the minimum number of telephone calls needed for everyone to know everything is .
See Also
1971 Canadian MO (Problems) | ||
Preceded by Problem 9 |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • | Followed by Last Question |