Mathematicians Doze Off

Yawning is popularly known to be contagious. It may also be an indication of a simple need to sleep or boredom. An alert participant in a boring class will not be surprised that an epidemic of yawning that started shortly after the beginning of the lecture left a few others dozing off a while into the lecture. The following problem (USAMO, 1986) then will come as reflecting on a "real world" situation:

Discussion

References

1. P. Zeitz, The Art and Craft of Problem Solving, John Wiley & Sons, 1999, pp. 120-123

Let us call the mathematicians A, B, C, D, E, and denote the time intervals that each was asleep A₁, A₂, B₁, B₂, on so on. We define a graph with vertices corresponding to these 10 intervals. In the graph, we join by an edge any two vertices corresponding to overlapping intervals. 5 mathematicians can be combined in C(5, 2) = 10 pairs, so the graph has at least 10 edges. It is well known that a graph with N nodes and more than (N - 1) edges is bound to have a cycle, which tells us that our graph does have one.

An application of graph theory has delivered a cycle of intervals: a finite sequence of intervals in which any two successive intervals overlap as are the first and the last. We show by induction that in a cycle there are three overlapping intervals, i.e. intervals with a common point.

We start with a cycle of three intervals, for which the claim is next to obvious. One has to consider just a couple of possible configurations to make a convincing case.

Assume the claim has been proven for (k-1)-cycles and consider a cycle a₁, ..., a_k, k > 3, of overlapping intervals. Let a be the union of a₁ and a₂, and consider the sequence a, a₃, ..., a_k of k-1 intervals. The sequence is a (k-1)-cycle of overlapping intervals, which by our assumption contains three intervals with a common point. If a is not among the three we are done. Otherwise, there are intervals b and c that share a point with a. The point belongs to at least one of a₁ or a₂. Which proves the claim.

By definition, a connected graph with no cycles is called a tree. (A disconnected graph with no cycle is a forest.) A tree with N nodes always contains N-1 edges. In other words,

This can easily be proved by induction. A tree with two nodes has a single edge, naturally. For a bigger tree, pick up a node and a path that starts there. In the absence of cycles, the path terminates at a node incident to a single edge. Such a node is called a leaf. If we remove a leaf with the adjacent edge, the remaining graph will remain a tree with one node and one edge less, which allows us to proceed with the inductive step.

A forest with N nodes and k trees (k connected components) has N - k edges.