Introduction

Consider the following simple problem.

Prove that the shape on the left cannot be completely tiled by 20 polygons of the types shown on the right.

The solution is rather simple: colour the shape in the following manner.

This gives 18 green hexagons, 21 orange hexagons and 21 blue hexagons. On the other hand, each triangular piece must cover three hexagons of distinct colours. Hence, if we could tile the figure completely with 20 pieces, we would have 20 hexagons of each colour, which is a contradiction. Thus such a tiling is impossible. ♦

Harder Variation

Now suppose we replace the above shape with the following.

It is still impossible to tile it with the two types of pieces as above. However, the colouring method fails to prove it since we would obtain an equal number of hexagons of each colour. Thus we need a better method.

The following technique can be generalized to prove that a similar shape of size N is tileable if and only if

Conway-Lagarias Method

Here, we will present the solution by John H. Conway and Jeffrey C. Lagarias in their paper “Tiling with polyominoes and combinatorial group theory” (1990). First we convert the problem to an equivalent one with polyominoes. We need to show that it is impossible to tile the left polyomino with the two triangular ones on the right (no rotation allowed).

Free Group on Two Generators

Let F be the free group on the two-element set {x, y}. To describe it concretely, we consider the set of all words in  Reduction in a word occurs when we remove two neighbouring occurrences of and E.g.

A word is said to be reduced if no further reduction is possible. Now we can write F as the set of all reduced words in

• Group composition in F corresponds to concatenation of words with reduction. For instance,

• The group identity is the empty word.
• To obtain the inverse of a word, we reverse the order and replace each (resp. ) by (resp. ) and vice versa. E.g.

For convenience, we write for m neighbouring copies of x and for m neighbouring copies of and similarly for  Thus is shorthand for

Polyominoes and Words

Now for each polyomino above, we obtain an element of F as follows. Start with a base point on the perimeter. We trace around the perimeter in a counter-clockwise direction, write for the directions of right, left, up, down respectively, and record the loop as a word upon returning to the base point.

For the large triangular figure, we pick the bottom-left corner as the base point and obtain the following word:

Change of Base Points

Now our definition of depends on our choice of base points. Let’s see what happens to when we switch to a different point on the perimeter. Let correspond to the path from the old base point to the new along the perimeter, and let be the new loop. Then from the diagram:

we have in the group F.

In other words, if we change the base point, the new loop is a conjugate of the old one.

Tiling

The process of tiling can be converted to a statement about group product. Suppose we place the two figures together as follows:

The perimeter for A is represented by (or a conjugate) while that for B is represented by Hence the resulting diagram has perimeter which is the product of the words for A and B in the group F.

Summary.

Suppose polygons are represented by words . Upon tiling , the resulting perimeter is represented by a word which can be obtained from via conjugation and composition.

Example

Thus, if our large triangular polyomino can be tiled by the smaller pieces, then lies in the normal subgroup N generated by a and b. This will be exploited in our proof.

Proving Our Main Result

We will construct a normal subgroup K of F such that .

Step 1: Map each word in F to a computer program.

Suppose we have a robot which starts by facing a certain direction (e.g. north). For each element in F, we turn it into a computer program by reading the word from left to right:

• : turn right 60°, walk forward 1m, then turn right 60° again.
• : turn left 60°, walk backward 1m, then turn left 60° again.
• : turn left 60°, walk forward 1m, then turn left 60° again.
• : turn right 60°, walk backward 1m, then turn right 60° again.

Let K be the set of all words in F which bring the robot back to its original position and orientation. Note that K is closed under composition and inverse so it is a subgroup of F.  Furthermore, it is a normal subgroup since if and , then is the program which does g, then h (which has no nett effect on the robot), then the reverse of g.

Step 2: Show that a, b and c are in K.

Indeed, for a and b we have:

Likewise it is easy to verify that

For c, we let be the canonical homomorphism. Since we have:

In particular, we have .

Step 3: Plot possible paths for the robot.

One easily sees that the robot must travel along the following lines:

The robot’s direction is indicated by the arrow in each disc; thus, it can only face in at most one direction at any spot. If the next instruction is x, the robot travels on the perimeter of a yellow triangle, along the given x orientation. If it is x^-1, the robot travels along the perimeter of a yellow triangle, counter to the given x orientation. The same holds for y and y^-1, but with the blue triangle.

Step 4: Define a homomorphism

Since each is a closed path, we may define to be the number of hexagons enclosed by the path. Here, the counting is oriented counter-clockwise – a loop which encloses a hexagon is counted +1 if the loop is counter-clockwise and -1 otherwise. This gives the desired homomorphism We have

and thus we have

Now if the original tiling were possible, we would require pieces. Hence c is obtained from the product of 12 conjugates of a and b (in F). Since K is normal in F, each conjugate a’ of a lies in K and furthermore Likewise for any conjugate b’ of b in F. From this, it follows that is even, which contradicts .

Thus our proof is complete. ♦