The blue dots below are draggable.

What is this about?

If five nodes of a plane lattice are chosen at random, any two of them define a line that contains other lattice points, and more specifically, the midpoint of the segment between the two points is necessarily a lattice point. Four points may not possess such a pair. The applet above illustrates this statement in case of the square grid.

The validity of the statement for four points is easily established with the help of the applet. The case of five points is also simple.

The midpoint of the segment joining points P(x₁, y₁) and Q(x₂, y₂) is given by M((x₁ + x₂)/2, (y₁ + y₂)/2). M is the lattice point if and only if x₁ and x₂ are of the same parity and so are y₁ and y₂. With 2 coordinates, there are four different parity pairs: odd/odd, odd/even, even/odd and even/even. Among five points, at least two are bound to have the same parity combination. The line joining any two such points is bound to contain other lattice nodes.

The proof makes use of the Pigeonhole Principle: If n objects are distributed between fewer than n boxes, at least one box must contain at least two of the objects. Most often the principle is taken for granted, but sometimes it is offered as an exercise, e. g., see [Graham], Ex. 3.8 and [Averbach], Ex. 6.32. [Graham] actually deals with a more general Dirichlet's box principle using integer arithmetic. The latter is also shown in Chapter 20 of Proofs from THE BOOK. [Averbach] proves the Principle by invoking the (bipartite) graph theory. The nicest ever and most convincing proof (without words) was recently published for n = 7.

The Pigeonhole Principle is simple and natural. Given its simplicity, the number and variety of its applications is utterly surprising. Its place in the tool chest of any professional problem solver is indispensible. As E. Barbeau, M. Klamkin and W. Moser put it ([Barbeau], p. 211), with an inspired choice of objects and boxes, several problems are rendered completely innocuous by this principle. It is equally true that those whose inspiration is begging may, in most cases, have difficulty fingering both objects and boxes. Chapter 20 of Proofs from THE BOOK collects several examples, to which applicability of the Pigeonhole is not at all obvious.

In the recent proceedings of a gathering in honor of Martin Gardner, we find two relevant and entertaining applications.

Place (by dragging) the ten words at the bottom of the applet into the ten cells that form a chain such that any two words adjacent in the chain, share one common letter.

The puzzle comes in two variants [Rodgers] that differ from one another ever so slightly. The words SON, HUT in one are replaced with SUN, HOT in the other. The latter is solvable, the former is not. The reason is that the two variants are represented by different graphs:

Obviously, a solution to the puzzle constitutes a Hamiltonian circuit on its graph. (A circuit in a graph is Hamiltonian if it passes through every node of the graph exactly once.) The first of the two is the famous Petersen graph that is known not to house any Hamiltonian circuits. In the second, Hamiltonian circuits are easily found even by trial and error. (M. Gardner's The Last Recreations contains a chapter on the Pigeonhole Principle and a chapter on Snarks that can't live without the Petersen graph.) A generalized version of the Pigeonhole is naturally used to show that the Petersen graph does not have Hamiltonian circuits.

The inventor, Tom Rodgers, suggests using the puzzle to amuse oneself at the expense of befuddled friends. Have 12 word scrub tiles ready and use 10 of them to arrange publicly in a chain. Then drop the tiles on the table. "Be careful to hold onto the HOT and SUN scrub with your thumbs, letting HUT and SON fall in their place. Your poor, befuddled victim will have no chance at finding a loop."

In the same volume, B. Epstein offers a no less bewildering party trick which is also based on the Pigeonhole Principle. But before I describe it, let's play a game. The task is to recognize a permutations of the numbers 1 through 10. Some numbers are hidden, others (at most 6 of them) are clearly shown. Sometimes the numbers appear in blue, sometimes in red. With such preliminaries, can you now name the hidden numbers? (For a training session we can use 5 numbers, of which at most 2 are shown.)

Believe me you can, for I shall presently reveal the secret of my selection. It follows from Dirichlet's box principle, that in any permutation of 10 distinct numbers there exists an increasing subsequence of at least 4 numbers or a decreasing subsequence of at least 4 numbers. (A general statement is due to P. Erdös and G. Szekeres, see [Aigner], p. 124.) These are the numbers that remain hidden. You'll know that the sequence is increasing if the numbers are red. It's decreasing if they are blue.

For a party trick, two persons should coordinate their efforts. The mathematical origins of the trick could be easily concealed by picking ten playing cards whose order is agreed upon in advance. Whenever a decreasing sequence turns up, deal cards in the reverse order, thus avoiding the dependence on color clues.

Dirichlet's box principle asserts that if n objects are put into m boxes, some box must contain at least ceil(n/m) objects, some box must contain at most floor(n/m). As an application, the task of writing this column consisted of five pieces (m = 5): programming the three applets (3), writing up the text in-between (1), and coming up with this paragraph (1) to end the column with. It took me n = 6 hours to complete the task. It follows from Dirichlet's box principle that one of the subtasks was bound to take at least ceil(6/5) = 2 hours. As a matter of fact, the last one did.

1. M. Aigner, G. Ziegler, Proofs from THE BOOK, Springer, 2000
2. B. Averbach, O. Chein, Problem Solving Through Recreatinoal Mathematics, Dover, 2000
3. E. Barbeau, M. Klamkin, W. Moser, Five Hundred Mathematical Challenges, MAA, 1995
4. B. Epstein, All You Need Is Cards, in Puzzlers' Tribute, D. Wolfe, T. Rodgers (eds), A K Peters, 2002
5. M. Gardner, The Last Recreation, Copernicus, 1997
6. R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.
7. R. Libeskind-Hadas, PWW: The Pigeonhole Principle, Math Magazine 75 (1) 2002, p. 39
8. T. Rodgers, A Scrub Tile Puzzle, in Puzzlers' Tribute, D. Wolfe, T. Rodgers (eds), A K Peters, 2002
9. D. Wolfe, T. Rodgers, Puzzlers' Tribute, A K Peters, 2002

Alex Bogomolny has started and still maintains a popular Web site Interactive Mathematics Miscellany and Puzzles to which he brought more than 10 years of college instruction and, at least as much, programming experience. In March 2002 the site has welcomed its 4,000,000^th visitor. Alex holds M.S. degree in Mathematics from the Moscow State University and Ph.D. in Applied Mathematics from the Hebrew University of Jerusalem. He can be reached at alexb@cut-the-knot.com

Copyright © 1996-2002 Alexander Bogomolny