Difference between revisions of "1971 Canadian MO Problems/Problem 10"
m |
|||
| Line 3: | Line 3: | ||
== Solution == | == Solution == | ||
| − | {{ | + | If all the n people know one distinct thing each, we can, without loss of generality, label them <math>P_1, P_2, \dots, P_n</math>. One way that is always possible is as follows: |
| − | + | 1. Starting at <math>P_1</math>, each <math>P_k</math> calls <math>P_{k+1}</math>, giving all his information, until we reach <math>P_n</math>, who now knows everything. | |
| + | 2. Starting at <math>P_n</math>, each <math>P_k</math> calls <math>P_{k-1}</math>, thus making <math>P_{k-1}</math> know everything as well. | ||
| + | This requires <math>2(n-1)=2n-2</math> telephone calls, since <math>P_1, P_2, \dots, P_{n-1}</math> make calls on step 1 and <math>P_n, P_{n-1}, \dots, P_2</math> 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 <math>P_k</math> to know everything, all the others must have made a telephone call at one time, or their information would be unknown. Thus, <math>n-1</math> calls are needed for some person to know everything. | ||
| + | We now examine step 2. If only one <math>P_k</math> knows everything, <math>n-1</math> calls must be made, because each of the others must be informed by someone. Thus, <math>n-1</math> 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 <math>2n-2</math>. | ||
== See Also == | == See Also == | ||
{{Old CanadaMO box|num-b=9|after=Last Question|year=1971}} | {{Old CanadaMO box|num-b=9|after=Last Question|year=1971}} | ||
[[Category:Intermediate Combinatorics Problems]] | [[Category:Intermediate Combinatorics Problems]] | ||
Latest revision as of 09:54, 27 April 2013
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 |
