# 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