Using your Head is Permitted

October 2012 solution

Let us define a graph that describes a tiling. First, we define the vertices of the graph as the set of points in the plane where one of the rectangles has a corner. Note that typically such places will be the positions of the corners of exactly two rectangles. The only exceptions are: (a) the corners of the big rectangle, that are only corners of a single small rectangle each; and (b) positions that are at an X-intersection of four rectangles.

Pick from each small rectangle a parallel pair of sides whose length is in S (arbitrarily, if both pairs are compliant). These will be the edges of the graph. We note that this is really a multigraph: a pair of vertices may have two parallel edges connecting them.

Now, begin at a corner and travel along the graph's edges as much as you can without using the same edge twice. The point you will get stuck in is another corner. The way to see it is that all other vertices have an even number of rectangles associated with them, and therefore an even number of edges.

Throughout, every motion in either axis was by an amount in S. Therefore, the total distance traveled in each axis is in S. Because we traveled from one corner of the large rectangle to another, this completes the proof.

Q.E.D.

As mentioned, Graham Hemsley sent me this riddle. He reached this solution independently, as well as the formulation of the riddle variant. Stan Wagon credits this solution to Michael S. Paterson of the University of Warwick. It appears here, in his classic compendium of fourteen proofs to the classic rectangle tiling problem, as proof number 7. I thank Oded Margalit for directing this beautiful riddle variation my way.

Back to riddle

Back to main page