AN ELEMENTARY PROOF OF TWO TRIANGLE-TILING
THEOREMS OF CONWAY AND LAGARIAS

Donald C. West
State University of New York
Plattsburgh, NY 12901

This work was done in 1990-91 and presented to AMS in fall 1991 at Temple University in a Special Session on Tiling. I have prepared this material for the web in 2002. I did it quickly with the help of OCR, so there may be errors. If you find errors, or anything suspicious, don't just point and laugh, let me know!

ABSTRACT

A triangular array of dots can never be tiled by three-in-line tiles, and can be tiled by three-in-a-triangle tiles only if the size of the array is congruent to 0, 2, 9 or 11 (mod 12). We give an elementary proof of these two results, not involving Conway's tile group.

J. H. Conway and J. C. Lagarias [1] develop an approach to tiling problems which uses a tile-boundary group. They use this approach to prove two specific theorems regarding tiling of a triangular array Tn of dots (n on a side).

THEOREM 1.1 The triangle Tn can be tiled by copies of T2
                             if and only if n = 0, 2, 9, or 11 (mod 12).

THEOREM 1.2 It is impossible to tile Tn with copies of the three-in-line tile.

They also show that these problems can not be solved by a "generalized coloring argument" and ask whether any elementary method can be used. The positive portion of Theorem 1.1 is proved by direct construction and induction.

Conway and Lagarias use their group method to prove the negative portions. We will use an elementary (though somewhat tedious) approach to prove the negative portions of both theorems.

We start by considering the more general question of tiling Tn with a mix of three-in-line tiles and little triangles. By counting the dots, we can show that n must be congruent to 0 or 2 (mod 3), and Fig. 1 shows that these cases can all be done.

Experiments with such tilings reveal a couple of equivalences of small tiling configurations which we will call X and Y (Fig. 1). Of course, case Y can occur rotated and upside-down, while X can occur in five other orientations in the triangular lattice.


Fig. 1. Canonical tiling of Tn and the moves X and Y.

Our main result is that any two tilings of Tn are equivalent in the sense that one tiling can be obtained from the other by a sequence of the two moves X and Y. This has a further implication. Assume that the original big triangle Tn is oriented with its point up. For any tiling of Tn, define the valence of the tiling to be the difference u-v where u (resp. v) is the number of triangular tiles which are point-up (resp. point-down). Since the moves X and Y do not change the valence, all tilings of Tn have the same valence. The canonical tiling in Fig. 1 shows that the valence is [(n+l)/3]. This implies that u-v>0 in case n>l, so at least one triangular tile is required in any tiling. This proves Theorem 1.2.

To prove Theorem 1.1, we notice that if we use only triangular tiles (no lines), the total number of dots is 3(u+v) = n(n+l)/2. Since u+v and u-v are either both even or both odd, we conclude that a necessary condition for a tiling by triangular tiles is that

It is easy to show ([1] p. 197) that this implies Theorem 1.1. (It may be worth noting that the valence of a tiling is just the value of the Conway-Lagarias homomorphism.)

Now let us state and prove our main result.

THEOREM 0. Any tiling of Tn by row-of-three tiles and triangle-of-three tiles can be converted, by a sequence of moves X and Y, to the canonical tiling in Fig. 1.

The proof will be by induction. Viewing the big triangle of dots as broken into slanted columns of width three, we will work across, column by column and work down each column. We suppose that the triangle is already tiled and, looking at a certain column, that all the columns to its left are tiled canonically. Using moves X and Y, without disturbing the good columns, we will rearrange the tiling until there is a triangular tile at the top of the column. Then, assuming that the new column is canonically tiled on some top segment, we will rearrange the tiling (not disturbing the good part) to get one more horizontal tile at the bottom of the good part (at the three big dots of Fig. 2).


Fig. 2. The induction hypothesis and a herringbone configuration.

The proof will be supported with several lemmas which promise us what we can expect when we encounter certain common, small configurations of tiles. The easiest of these will be called the Herringbone Lemma, because of the appearance of the configuration involved (Fig. 2). The lemmas will be given as pictures; the arrow indicates that when the first configuration appears, the tiles below and to the right may be rearranged, using moves X and Y to achieve the second configuration.

LEMMA A. (Herringbone) Any configuration whose top is the top of a herringbone (Fig. 3 (left)) may be converted, changing only tiles in the band directly below the two top tiles, to get a triangular tile at the top.

Proof. The proof is done in three cases, because the dot wedged just below the two top tiles can be covered in just three ways, shown in Fig. 3(right).

The first case is converted by two rotations Y. In the second case, we use X and then Y. The third case continues a herringbone, which must ultimately end, because we are tiling a finite region. It ends with one of the two earlier configurations. When it ends, we can get a triangular tile at the bottom which we can bubble up to the top by repeated rotations Y.


Fig. 3. The Herringbone Lemma: the statement (left) and proof (right) of Lemma A.

We can use this same argument and the Herringbone Lemma to prove the first of our two induction steps. Proof of the first induction step. Assuming that all the columns to the left are tiled canonically, we need to show that we can rearrange the tiling to get a triangular tile at the top of the new column. The top dot can be covered in three ways. If it is covered by a triangular tile, we are done. If the top dot is covered by a straight tile, then we look at the dot wedged just below it, and consider the three ways it can be covered. If it is covered by a triangular tile, we apply a rotation Y to move the triangle to the top. If it is covered by a straight tile parallel to the first, we apply move X. In the third case, we apply the Herringbone Lemma.

The remaining lemmas are similar in spirit. They each say that if we encounter a certain small configuration in our given tiling, we can always change it in a specified way, disturbing tiles in at most a certain specified region below the configuration and to the right. We will label the remaining rearrangement lemmas with letters B, C ...G and group them by type, giving only their diagrams. The Herringbone Lemma is included, for completeness. We may think of assertions A, B and C as saying that if a local configuration has a point at the top, then that point may be made to be the top of a triangular tile (Fig. 4 (left)).

Assertion C has an alternate form which lumps it together with D and E and the second inductive step of our proof. These all say that we can rearrange to place a horizontal tile under a given horizontal tile in a 120 degree sector (Fig. 4(right)). These four are all proved in the same way.


Fig. 4. Lemmas A ... E in two groups, by type.

Assertion F supports the proofs of C, D and E, stating that we can trade a certain triangular tile for a horizontal tile (Fig. 5).

Assertion G is really a statement about any one of several related configurations. Just two of them are illustrated in Fig. 5. The common feature is that they all have a single hole at the bottom. The assertion is that the dot in this hole can always be covered with the top of triangular tile.


Fig. 5. Lemma F and two cases of Lemma G.

The six assertions B to G must be proved together, because the proof of each one uses one or more of the other assertions. This sounds like circular reasoning, but it is not. We use induction, as we did in the Herringbone Lemma. For example, we might have configuration G with B below it and C below that, etc. Ultimately, this chaining must stop with a configuration at the bottom which we know how to handle. We then work our way up, as we did in the proof of the Herringbone Lemma.

The proof of Lemma B is shown in Fig. 6 and Lemma E is treated in Fig. 7. Five cases correspond to the five tiles that can cover the dot wedged in the 120 degree sector. In this proof, Lemmas D and G are applied not vertically, but at a 30 degree slant down to the right. Lemmas C and D and the main induction step are proved in the very same way as Lemma E. Fig. 7 shows the proof of Lemma F. The proof of G simply uses A, B and C, and is omitted.


Fig. 6. Proof of Lemma B.


Fig. 7. Proof of Lemma E;
Lemmas C and D and the main induction
step are proved in the very same way.


Fig. 8. Proof of Lemma F.


REFERENCES

1. J. H. CONWAY AND J. C. LAGARIAS, Tiling with Polyominoes and Combinatorial Group Theory, J. Combin. Th. A, 53, (1990) 183-208.

2. W. THURSTON, Conway's Tiling Groups, Amer. Math. Monthly 95 (1990), Special Geometry Issue.


to Don West's Page

Copyright 2002 All Rights Reserved