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:

During a certain lecture, each of five mathematicians fell asleep exactly twice. For each pair of mathematicians, there was some moment when both were asleep simultaneously. Prove that, at some moment, three of them were sleeping simultaneously.

Discussion

References

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.

Trees

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,

For trees, the number of edges is one less than the number of vertices.

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.

71945621