A Rectangular Tiling Theorem



Rectangular Tiling Theorem
If a finite number of rectangles, each of which has at least one integer length side, exactly tile a rectangular space, then this rectangular space also has at least one integer length side.

An early proof of this theorem used complex integration, but there are very simple proofs of the theorem. David MacKay has posted two simple proofs on his website that, he says, a 10-yesr old could understand. A paper by Stan Wagon, in The American Mathematical Monthly Vol. 94, No. 7 (Aug. - Sep., 1987), pp. 601-617, gives 14 proofs of the theorem. He shows that at least 11 of these proofs are independent of each other, by showing that they have different generalisations. His 12 generalisations include: generalising integer (lengths) to any subgroup of the real numbers, e.g., fractional (lengths); any finite number of dimensions, e.g. rectangular blocks (3-D); on a cylinder instead of a plane; on a torus; and several others.


For two of the proofs (and some others), computer programs can be written that illustrate the proofs. One is the second of the proofs in MacKay's article (7th proof in Wagon's paper) where a program can construct a path consisting of integer length tile edges from one corner of the tiled space to another corner. The other is the 10th proof in Wagon's paper, although the reduction rule in the proof is a special case of the reduction rule used in my program. Provided the shortest tile, S say, on (respectively under) an H-link is of integer height, h say, the H-link can be moved up (respectively down) by h units, as in the proof, whether or not the other tiles on the same side of the H-link as S are V-tiles. Similarly, this holds for V-links.
The two computer programs are DrawScript programs for RISC OS, which output to vector graphics windows.
An example of a rectangular tiling of a rectangular space by 128 I-tiles (tiles that have at least one side of integer length) showing some paths consisting of integer length edges (I=paths) is here. This illustrates part of the second proof in MacKay's article (7th proof in Wagon's paper). The diagram was drawn by a DrawScript program. The I-paths are complete in the sense that, starting at any end-point of an integer length edge (I-edge) and continuing along I-edges without repeating an edge, one either gets back to the starting point, giving a loop, or one ends in a corner. In the latter case, the path traced out is part (or the whole, if starting in a corner) of a corner to corner path. There is a unique complete I-path asssociated with any starting point.
It needs to be pointed out that the proof and the program work only if, for any tile that has both integer length and integer width, only one of the two pairs of parallel edges is included in the graph (aka network), it doesn't matter which.

The reduction rules used in the other program, which I call cut-and-glue rules are explained in "Two cut-and-glue-rules". Using the same example of 128 I-tiles, a diagram shows all the places where the first of the two rules can be applied, and another diagram shows the result after the "above the cross-bar" orientation of this rule has been applied by the program scanning the tiling from top to bottom (and left to right at each height) for the above the cross-bar configuration of tiles, indicated in the first diagram by green atop these cross-bars. The rectangular space is now tiled by 90 I-tiles. Note that, although there are only 34 places in the original tiling where this orientation of the rule can be applied (the green bars), in a few of them a reduction of more than 1 tile is achieved.