1971 Canadian MO Problems/Problem 10

Problem

Suppose that $n$ people each know exactly one piece of information, and all $n$ pieces are different. Every time person $A$ phones person $B$ , $A$ tells $B$ everything that $A$ knows, while $B$ tells $A$ 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 $P_1, P_2, \dots, P_n$ . One way that is always possible is as follows: 1. Starting at $P_1$ , each $P_k$ calls $P_{k+1}$ , giving all his information, until we reach $P_n$ , who now knows everything. 2. Starting at $P_n$ , each $P_k$ calls $P_{k-1}$ , thus making $P_{k-1}$ know everything as well. This requires $2(n-1)=2n-2$ telephone calls, since $P_1, P_2, \dots, P_{n-1}$ make calls on step 1 and $P_n, P_{n-1}, \dots, P_2$ 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 $P_k$ to know everything, all the others must have made a telephone call at one time, or their information would be unknown. Thus, $n-1$ calls are needed for some person to know everything. We now examine step 2. If only one $P_k$ knows everything, $n-1$ calls must be made, because each of the others must be informed by someone. Thus, $n-1$ 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 $2n-2$ .

1971 Canadian MO (Problems)
Preceded by Problem 9	1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 •	Followed by Last Question

Page

Toolbox

Search

1971 Canadian MO Problems/Problem 10

Problem

Solution

See Also