The Art and Craft of Problem Solving

110 CHAPTER 4 THREE IMPORTANT CROSSOVER TACTICS

are the "objects" and we join vertices with edges if the corresponding objects are "re­

lated."

If you're not yet convinced, look at the following problem. Don't read the analysis

immediately.

Example 4.1.1 (USAMO 1986) During a certain lecture, each of five mathematicians

fell asleep exactly twice. For each pair of these mathematicians, there was some mo­

ment when both were sleeping simultaneously. Prove that, at some moment, some

three of them were sleeping simultaneously.

Partial Solution: Let us call the mathematicians A,B,C,D,E, and denote the

time intervals that each was asleep by Al ,A 2 ,B, ,B 2 , etc. Now define a graph whose 10

vertices are these time intervals, with vertices connected by an edge if the time intervals

overlapped. There are (�) = 10 pairs of mathematicians, I so this graph must have at

least 10 edges. Here is one example, depicting the situation where mathematician A's

first nap overlaps with C's first nap and E's second nap, etc. Notice that Al and A2

cannot be joined with a vertex, nor can B, and B 2 , etc., since each mathematician took

two distinct naps.

This particular graph contains the cycle CIAIE 2 B 2 CI. By this we mean a closed

path that "travels" along edges. A cycle is helpful, because it constrains the overlap

times. It is easiest to see this by "stacking" the intervals. Here is one possibility. Time

is measured horizontally. Notice that each nap interval must overlap with its vertical

neighbor(s).

------- cl

We will show that three different intervals must overlap. Since C, and B 2 overlap, and

CI and A l overlap, we are done if B 2 and Al overlap within CI. If they don't (as in

I Read Section 6. 1 if you don't understand the notation (;).