Simple Proofs of a Rectangle Tiling Theorem |
Cavendish Laboratory
Madingley Road
Cambridge CB3 OHE
mackay@mrao.cam.ac.uk
May 27, 2003 - Draft 1.8.
(for the latest paper copy of this document, see the website)
AbstractIf a finite number of rectangles, every one of which has at least one integer side, perfectly tile a big rectangle, then the big rectangle also has at least one integer side. I present two proofs of this theorem, both accessible to a ten-year-old. The proofs generalize to other situations. |
Here are three theorems. In all three, a large rectangle is partitioned into smaller rectangles, with sides parallel to those of the large rectangle.
Do these theorems have simple solutions? Opinions vary. When I was introduced to theorem 2, I heard that it was celebrated for having an elementary solution that was hard to find. However, according to the IBM `Ponder This' website (IBM 1999a),
Although this problem (theorem 1) may appear simple at first, the solution is actually fairly complex.
In fact, all three theorems have proofs that a ten-year-old can understand. [Fourteen proofs of theorem 1 were published by Wagon (1987), but I was not aware of this when I wrote the present paper.]
To maximize your enjoyment of this puzzle, you may wish to think about these theorems before scrolling down. |
In order to prove the second theorem it suffices to prove the first, since, taking an instance of theorem 2, if the rational sides have lengths {m/n}, we can scale up all the lengths by a factor of the lowest common multiple of {n}, thus converting all the rational sides to integer sides.
So, how should we prove theorem 1? And what about theorem 3?
Proof by complex integration
A standard proof of theorem 1 (IBM 1999b) involves integrating the complex function e2πi (x+y) over the two-dimensional plane. The integral over any rectangle is zero if and only if at least one side is an integer; so the integral over each small rectangle is zero; the integral over the big rectangle is the sum of the small rectangles' integrals, so it equals zero too; therefore the big rectangle has an integer side.
This proof is probably not accessible to most ten-year olds; nor is the second solution given at (IBM 1999b), which involves large prime numbers. And neither of these proofs helps prove theorem 3.
I now present two proofs of theorem 1, both accessible to ten-year-olds. The first proof is similar in character to the complex integral proof sketched above. The second proof uses a completely different approach, which can be applied immediately to theorem 3. Both proofs have been published before (Wagon, 1987).
Figure 1. Illustration of the checkerboard proof. Dashed blue lines are an integer grid. The checkerboard squares are of size 1/2. In the lefthand example (a), the central small rectangle violates the constraint of the theorem: it has both sides non-integer. In the righthand example (b), every small rectangle has one side of integer length. Every small rectangle covers equal amounts of black and white, so the large rectangle must do the same. |
Take the big rectangle and align its bottom left corner with a half-integer checkerboard - that is, a checkerboard whose squares have side 1/2 (figure 1). Let the bottom left corner be black.
If the big rectangle has both sides non-integer, then the black area covered will exceed the white area covered; and if the black and white areas covered are equal then the big rectangle must have an integer side (figure 2).
However, every small rectangle, since it has an integer side, must cover equal areas of black and white.
So the big rectangle must cover equal areas of black and white and so must have an integer side.
Figure 2. A non-integer rectangle whose bottom-left corner is aligned with the integer grid always
covers more black than white. (The origin of the integer grid is at the bottom left of a
black square.)
Here we zoom in on the upper right corner of the rectangle in figure 1, which must look
like one of the three pictures in the top row. For the purpose of finding the excess black
area, we can transform the first situation into the second and the second into the third
by the constructions shown in the bottom row, which leave unchanged the difference
between black and white coverage. In the third situation, only black area is covered,
therefore in all three situations, the black area exceeds the white area.
For those who prefer formulae to symbolic proofs, the excess black area for a rectangle
with upper corner at (x, y) is
|
Radford Neal pointed out the similarity of these puzzles to the task of proving that the game of Hex cannot end in a draw.
In the three rectangle puzzles, at least one of the big rectangle's sides must have a special property. Similarly, in Hex, when all pieces have been played, at least one player must have connected his two sides together (Gale and van Rijswijck 2002). (In fact, in Hex, exactly one player achieves this result.)
How can we apply this analogy?
Depending whether we wish to prove theorem 1, 2, or 3, we will call a number special if it is integer, rational, or algebraic, respectively. The sum and difference of two special numbers are also special. We define a point (x; y) in the plane to be special if both coordinates x and y are special.
Take the set of small rectangles, and associate with each small rectangle four vertices and two edges (figure 3). The four vertices are the four corners of the rectangle. The two edges are two parallel sides of the rectangle that are both special in length. (Every small rectangle has two such special edges, by the statement of the problem.)
Figure 3. Make a graph in which, for every small rectangle, there are two edges corresponding to two parallel `special' edges. |
Lemma 1 If a vertex is special, then its neighbouring vertex is also special.
We now define a graph by identifying all the vertices that have identical coordinates (figure 4). In this graph there may be double edges connecting two vertices. Such double edges are not merged into a single edge.
Figure 4. Vertices identified. |
Lemma 2 Apart from the four vertices at the corners of the big rectangle, which have degree 1, all other vertices have degree two or four.
Let's align our coordinate system such that the bottom left vertex of the big rectangle is at the origin. This vertex is thus special. Now, make a walk through the graph starting from this vertex. At each step of the walk, advance along an edge that has not been traversed before to another vertex. Since every vertex (other than the four corner vertices) has even degree, there will always be another edge to traverse, unless we move into one of the corner vertices. There are a finite number of edges, so we must eventually move to a corner vertex. It's impossible that this corner vertex is the one we started from (since it had degree one, and we never traverse any edge twice). Thus our walk must have taken us to another corner. By lemma 1, our walk establishes that the big rectangle has two special corners, thus it has at least one side that is special in length.
Figure 5. The red walk starts from the bottom-left corner and proceeds through the graph along special edges. Eventually the walk emerges at another corner (the bottom- right corner, as it happens) and thus becomes a witness to the fact that those two corners differ by a special distance. |
Both proofs can be applied to the analogous problem in higher dimensions where each small hyperrectangle has one `special' dimension.
Thanks to Graeme Mitchison, Geoff Hinton, Radford Neal, and Tadashi Tokieda.