Which rectangles can be tiled with L-trominos, when only two orientations are allowed?

Question

This is a question that I got after reading this: https://www.cut-the-knot.org/Curriculum/Games/LminoRect.shtml. (This link already gave me the same result as theorem 1.1 of the article https://www.sciencedirect.com/science/article/pii/S0012365X08000629.) I hope that some people here might be able to help me solve it.

Let $m$ and $n$ be integers greater than 1. Find all pairs $(m,n)$ such that it is possible to tile an $m\times n$ table with right-oriented L-shaped trominos. The pictures below shows what right/left-oriented trominos are. (No rotations allowed. So, left-oriented trominos can't be used.)

Clearly either $m$ or $n$ must be divisible by $3$. Two right-oriented trominos can be combined to form a $2\times 3$ rectangle. Therefore it can be seen that if $6\mid mn$, then the table can be tiled with these trominos. I tried to deal with the case where $3\mid mn$ but $2\nmid mn$. It seems that there is always a $3\times 1$ or $1\times 3$ leftover. My guess is that $6\mid mn$ is indeed the necessary and sufficient condition. Please help!

Answer 1

This is a very cool question! This answer is that $6\mid mn$ is indeed a necessary condition to be able to tile an $m\times n$ rectangle with right-handed L-trominos. However, to prove this, a coloring argument is not sufficient; you need to use a noncommutative invariant.

To solve this, we use the tiling group invented by Conway and Lagarias. Given a region $R$ in the rectangular grid, and a set of tiles $T_1,\dots,T_m$, we can ask whether $R$ can be tiled with translated copies of $T_1,\dots,T_m$. Define the "combinatorial boundary" of $R$, denoted $\partial R$, to be the sequence of directions you get when you start at an arbitrary point on the boundary of $R$, and trace around $R$ counter-clockwise, making a unit step each time. This corresponds to an element of the free group on two generators, $x$ and $y$, using the correspondence $$ x = \text{East},\quad x^{-1}=\text{West},\quad y = \text{North},\quad y^{-1}=\text{South}. $$It turns out that if you take the free group $F[x,y]$, and introduce relations corresponding to the boundaries of the tiles, $\partial T_i$, then you get powerful tiling invariant.

Theorem (Conway, Lagarius, 1990): If $R$ is a simply connected region in the rectangular grid which can be tiled with translated copies of $T_1,\dots,T_m$, then $\partial R$ is the identity element when viewed as an element of the group $$T:=\langle x, y \mid \partial T_1=\dots=\partial T_m=1\rangle $$

In particular, to prove $R$ cannot be tiled, it suffices to show $\partial R$ is nonzero as an element of $T$.

In our case, the boundaries of the two tiles are described by the sequences (East, East, North, North, West, South, West, South), and (East, North, East, North, West, West, South, South), so the two relations for our group are $$ \partial T_1 =x^2y^2(x^{-1}y^{-1})^2,\qquad \partial T_2=(xy)^2x^{-2}y^{-2} $$Let $m$ and $n$ be odd integers such that $3\mid mn$. The combinatorial boundary of the $m\times n$ rectangle is $$\partial R = x^n y^m x^{-n} y^{-m}.$$ As long as we can show that $\partial R$ is nonzero in the group $$ \langle x,y\mid x^2y^2(x^{-1}y^{-1})^2=(xy)^2x^{-2}y^{-2}=1\rangle, $$then we will have proved the rectangle is not tile-able. Doing this is no easy feat.

Conway and Lagarius introduced a very powerful tool for analyzing this group. Consider the 3.6.3.6 tiling of the plane; this consists of regular hexagons and equilateral triangles, both with side length $1$, such that any two triangles only meet at a vertex. Triangles come in two orientations, say, upward pointing and downward pointing. Any element of the free group $F[x,y]$ determines a path along the edges of the 3.6.3.6 tiling. Starting from an arbitrary base vertex, you read the free group word from left to right, and take steps as follows:

• $x$ means you take one step which follows the boundary of the nearest upward-pointing triangle, going counter-clockwise. For $x^{-1}$, you go clockwise.

• $y$ means you take one step which follows the boundary of the nearest downward-pointing triangle, going counter-clockwise. For $y^{-1}$, you go clockwise.

When you do this procedure using the two boundaries of the right-handed trominos, $\partial T_1$ and $\partial T_2$, each path will enclose exactly one upward-pointing triangle, one downward pointing triangle, and one hexagon. This implies that if the free group word for $\partial R$ is the identity in the tile group, then it must enclose an equal number of upward point triangles, downward pointing triangles, and hexagons.

However, $\partial R= x^n y^m x^{-n} y^{-m}$ actually encloses zero of each of the three shapes, so this is not enough to conclude $\partial R\neq 1$. We need to strengthen this invariant as follows. Consider a square, where the two horizontal edges are labeled "$x$", and the two vertical edges are labeled "$y$". Any free group element $F[x,y]$ also determines a path on the vertices of this square, where $x$ and $x^{-1}$ mean to move along the nearest $x$ edge, and $y$ and $y^{-1}$ mean move along the nearest $y$ edge. Our two tromino tiles trace out paths with wind exactly once around the center of this square, either clockwise or counter-clockwise. This means that if you keep track of the 3.6.3.6 path and the square path simultaneously, then any region which can be tiled with trominos must satisfy

• # upward triangles = # number downward triangles = # number hexagons, and

• # hexagons $\equiv$ # number of times winding around the square $\pmod 2$.

Finally, we can prove $R$ cannot be tiled when we have $3\mid mn$ but $6\not\mid mn$. You can check that while $\partial R$ encloses zero triangles and hexagons, it does wind exactly once around the square. Since the bullet point in the second invariant is violated, we conclude that $R$ cannot be tiled.

---

• J.H Conway, J.C Lagarias, Tiling with polyominoes and combinatorial group theory, Journal of Combinatorial Theory, Series A, Volume 53, Issue 2, 1990, Pages 183-208, https://doi.org/10.1016/0097-3165(90)90057-4.

Answer 2

Adding my old answer as a seperate post, per request of
Mykola Hordeichyk.

Let's rephrase your problem in terms of hexagonal tilings. Let $H_{m,n}$ be a rhombus-like shape comprising $m\times n$ hexagonal cells, consisting of $m$ rows of hexagons stacked on top of each other, with $n$ hexagons per row. Each row is offset by half a hexagon relative to the row below. Also, define a "trihex" to be a tile consisting of three hexagonal cells which all share a common vertex. Then, the following problem is equivalent to yours:

For what values of $m$ and $n$ can $H_{m,n}$ be tiled with trihexes?

This equivalence is easily seen by applying something like a shear transformation to the original rectangle. Applying the same shear transformation to the two possible right-handed trominos results in the two orientations of a trihex tile (upward pointing and downward pointing).

Furthermore, define a "tribone" to be a tile consisting of three hexagons in a row. These come in three possible orientations. John Conway developed a noncommutative tiling invariant which applies to both tribones and trihexes, which was further explored by William Thurston. In the paper by Thurston cited below, he proved the following.

Proposition (Thurston): Suppose that a subset of the hexagonal grid can be tiled with a combination of trihexes and tribones. Among all such tilings, the parity of the number of tribones is invariant.

I can give a rough sketch of the proof, using ideas from my other answer. You can show that trihexes and tribones both determine pairs of paths, one in the trihexagonal tiling of the plane, and one on a square. It turns out that both tribones determine paths which wind clockwise around exactly one hexagon, and which wind once around the square either clockwise or anticlockwise. This means that as you build a region out of trihexes, the quantity $$(\text{# hexagons enclosed}) + (\text{# squares enclosed})\pmod 2$$ is preserved. However, it turns out the tribone encloses zero hexagons and one square, so adding a tribone flips the quantity. This shows that in any two tilings of the same region by tribones and trihexes, the difference in the number of tribones must be even.

Finally, we use this proposition to solve your problem. Suppose that $m$ and $n$ are odd integers such that $3\mid mn$. This means that $H_{m,n}$ can be tiled by tribones. The number of tribones used is $mn/3$, which is odd. Therefore, the Proposition implies that any tiling with tribones and trihexes must have an odd number of tribones. In particular, a tiling with zero tribones is impossible, so $H_{m,n}$ cannot be tiled by trihexes alone.

---

• Thurston, William P. Conway’s Tiling Groups. The American Mathematical Monthly, vol. 97, no. 8, 1990, pp. 757–73. JSTOR, https://doi.org/10.2307/2324578.