Integers and Rectangles:
Two Simple Proofs

A curious problem has been discussed by Stan Wagon not so long ago (also, in [Which Way Did The Bicycle Go?, #14].

In the paper, Wagon listed and discussed fourteen essentially different solutions that ranged from elementary to those that used integrals, graph theory, or topology (Sperner's lemma).

The most elementary solution was given by R. Rochberg and S. K. Stein. Another simple solution has been published by P. Winkler after Wagon's paper came out. Here, I'd like to present one other elementary proof from the paper (#7 by Michael Paterson) and a more recent proof by Andrei Gnepp [Zeitz, pp. 108-109]. The latter would be 15.5 according to the enumeration used on these pages.

The applet below helps understand the solutions. Both solutions show that the problem can be generalized by replacing the word "integer" with the word "algebraic", or, say, "constructible". In fact, it remains true if we consider only positive members of an additive subgroup of the real numbers. Let's call the members of the selected set special. The sum of special numbers is special and so is their difference, provided it's positive. A point (x, y) in the plane is special if both of its coordinates are special. A rectangle is called special if at least one of its dimensions is special.

Assume a big rectangle is tiled with small ones, each of which has a special side. In the applet the ones with special width are colored dark orange and those with special height red: H- and V-tiles, respectively. In case where both dimensions are special, the color assignment is arbitrary and can be changed be clicking twice on the rectangle. (Clicking twice is not the same as a double click.)

The applet allows one to add or remove rectangles, select one at a time, and change dimensions of the selected rectangle. All rectangles are draggable.

The start up configuration is taken from Winkler's book. So, the H-tiles are dark orange the V-tiles are red.

We shall assume that the ambient rectangle is so located as to have its lower left corner special. We also assume that the sides of the rectangle are parallel to the coordinate axes.

An important observation to make is that if one of the corners of a special rectangle is special then either all the remaining corners are special or exactly one additional corner is. A rectangle can't have just three special corners. For, if it has three corners special, then both of its dimensions are necessarily special and hence the fourth corner is also special. A special rectangle may only have an even number of special corners: 0, 2, or 4.

The applet is more relevant to the solution by Michael Paterson (#7 from Wagon), and this is the one will begin with.

With a tiling of the ambient rectangle we shall associate a graph whose set of nodes is exactly the set of corners of the rectangular tiles. (These of course include the four corners of the ambient rectangle itself.) In addition, in a V-tile we shall join the corners by two (essentially) vertical edges and in an H-tile by two (essentially) horizontal ones. The edges are drawn in the interiors of the rectangles.

We now make a second important observation:

1. The nodes of the graph associated with a tiling that correspond to the corners of the ambient rectangle have degree 1.
2. The degree of any other node is even: either 2 or 4.

Let's traverse the graph starting with the lower left node and minding not to traverse any edge twice. We may or may not end up with an Euler path, but when we reach a dead end, the last node in the path is bound to have a degree one. In other words, the constructed path will have joined to corners of the ambient rectangle. Note that any node of the graph adjacent to a special node is special. Since we began with a special node, all nodes on the path are bound to be special, the end point in particular. Depending on where the path ends, at least the two dimensions of the ambient rectangle is special, thus the rectangle is itself special.

The proof by Andrei Gnepp [Zeitz, pp. 108-109] is even simpler. Since all tiles are special, each has an even number of special corners. If we add up those numbers over all tiles, the result - denoted S - is bound to be even. (This is one of the fundamental facts of graph theory: the sum of the degrees of all nodes is even.) As far as the nodes off the graph are concerned, S overcounts some nodes. As we already observed, some of the internal nodes are counted twice, while others are counted four times. The corners of the ambient triangle might have been counted once. Let S₁, S₂, S₄ be the number of nodes that were counted 1, 2, or 4 times, respectively. Obviously S₁ is not 0. We see that

from which it follows that S₁ is even. So that the ambient rectangle has at least two special corners and is itself special.

References

1. J. Konhauser, D. Velleman, S. Wagon, Which Way Did the Bicycle Go?, MAA, 1996
2. D. MacKay, Simple Proofs of a Rectangle Tiling Theorem
3. S. Wagon, Fourteen Proofs of a Result About Tiling a Rectangle, Am Math Monthly, Vol. 94, No. 7 (Aug. - Sept., 1987), 601-617.
4. P. Winkler, Mathematical Puzzles: A Connoisseur's Collection, A K Peters, 2004, pp.6-7
5. P. Zeitz, The Art and Craft of Problem Solving, John Wiley & Sons, 1999

Integer Rectangles

• Rectangle on a Chessboard: an Introduction
• Rectangle on a Chessboard: Nathan Bowler's Proof
• Integers and Rectangles: Peter Winkler's Proof
• Integers and Rectangles: Two Simple Proofs
• Integers and Rectangles: a Proof by Induction

|Contact| |Front page| |Contents| |Algebra| |Store|

Copyright © 1996-2012 Alexander Bogomolny