1986 USAMO Problems/Problem 2

We shall assume to the contrary that there was never a time when three mathematicians were sleeping simultaneously, and derive a contradiction.

As a subtle but logically necessary note, we will assume without loss of generality that no two events (an event is one mathematician either falling asleep or waking up) happen at the same time.

Rationale: Consider a group of events happening simultaneously--i.e., there is a moment before any of the events have happened, and there is a moment after all the events have happened, but there are no moments in which at least one but not all of the events have happened. If there is a valid timeline--i.e. one in which every pair of mathematicians was simultaneously asleep at some moment, but in which no three mathematicians are simultaneously asleep at any moment--containing a group of simultaneous events, then there is also a valid timeline in which that group of events is broken up into a sequence; you can construct the second timeline by putting the "mathematician wakes up" events first and the "mathematician falls asleep" events last. (In the first timeline, there were n mathematicians asleep in the moments immediately before the group of events, and m mathematicians asleep immediately afterwards; in the second timeline, there will be additional moments when n-1, n-2, ..., k, k+1, ..., m-1 mathematicians were asleep. If the first timeline is valid, then n and m are both less than 3, so the additional intermediate moments will not violate the "no 3 asleep at once" rule; and since we did not remove any moments, if the "all sleeping-pairs" rule was satisfied in the first timeline, then it is satisfied in the second timeline.) So the existence of any valid timeline implies the existence of a sequential valid timeline.

We have (5 choose 2) = 10 sleeping-pairs of mathematicians to account for. Also, since 5 mathematicians each fell asleep 2 times, we have a total of 10 occasions on which a mathematician fell asleep. Now, if two mathematicians are ever asleep simultaneously, then one of them fell asleep while the other was already asleep. However, because of the "no three asleep at once" rule, if a mathematician falls asleep, then at most one other mathematician could have been asleep already. Therefore, each occasion when a mathematician falls asleep can account for at most one sleeping-pair. It would appear that we have just enough to make it. However, when the first mathematician falls asleep, no other mathematicians are asleep...

Hey, wait a minute. Couldn't one mathematician, or even two, have been already asleep when the lecture started? In fact, the wording of the problem does not forbid this, and this permits us to construct an easy counterexample:

Call the mathematicians A,B,C,D,E. A starts out asleep. B sleeps; A wakes; C sleeps; B wakes; D sleeps; C wakes; E sleeps; D wakes; A sleeps; E wakes; then, C sleeps; A wakes; E sleeps; C wakes; B sleeps; E wakes; D sleeps; B wakes; A sleeps; D wakes. This creates, in order, the sleeping-pairs AB, BC, CD, DE, EA, then AC, CE, EB, BD, DA; each mathematician falls asleep and wakes up exactly twice, and at no time are three mathematicians asleep.

Well, this must be considered a hole in the problem as written. However, if we add the (nontrivial) assumption that the mathematicians were all awake when the lecture began, then it follows that the first occasion when a mathematician falls asleep can only account for zero sleeping-pairs, and the remaining 9 occasions can only account for 9 sleeping-pairs, and so there must be some pair of mathematicians that are not simultaneously asleep during the lecture. So our assumption to the contrary implies an impossible sequence of events. Therefore, that assumption must be wrong, and there must be a moment when three mathematicians are asleep.