Problem: (1986 USAMO - #4) 5 professors are attending a lecture. During the lecture, each of them falls asleep twice and between each pair of professors they are asleep at the same moment at least once. Prove that three of them are asleep at the same moment. [Reworded]
Solution: This is an interesting problem and a cool application of the Pigeonhole Principle.
All the "moments" are treated as the start of an interval.
For each professor, there are 2 falling asleep moments, making 10 total. Call this set of moments S. For each pair, there is a moment at which both are asleep, making 10 also. Call this set of moments T. If any two moments in T are the same, we are done. If not, then they are all different.
We can correspond each moment in T with a moment in S because at the beginning of any interval in which two professors are sleeping, one of them must have just fallen asleep. However, the first 2 moments in S have to come before or at the same time as the first moment in T (since two have to fall asleep before two can be sleeping at the same time). Then the remaining 9 moments in T have to correspond with the 8 other moments in S, which means (by Pigeonhole) that 2 moments in T must be the same. Contradiction.
Hence there must be some moment at which three professors are asleep. QED.
--------------------
Comment: The proof of this is not extremely difficult, but it requires some innovative thinking to discover.
--------------------
Practice Problem: (1989 USAMO - #2) The 20 members of a local tennis club have scheduled exactly 14 two-person games among themselves, with each member playing in at least one game. Prove that within this schedule there must be a set of 6 games with 12 distinct players.
No comments:
Post a Comment