Can every polyomino of even size be tiled by $L$-trominoes when scaled up by a factor of $3$?

Question

The $L$-tromino does not tile a $3\times 3$ square. However, it can tile $3\times3$ squares glued together in various ways:

                                                                   

I am interested in the polyominoes $P$ for which the $L$-tromino can tile a copy of $P$ scaled up by a factor of $3$ along both axes.

It is easy to see that some $P$ will fail, such as any $1\times k$ rectangle for odd $k$. However, it appears that every polyomino $P$ with an even number of cells can be tiled by $L$ shapes when it is scaled up by $3$. This holds for all polyominoes $P$ with $2, 4, 6, \ldots, 12$ cells.

One might be tempted to argue from induction: given a polyomino $P$ of size $2k$, subtract a $3\times 6$ domino from $P$ (which can be tiled), and tile the remaining size-$(2k-2)$ polyomino with $L$s by the inductive hypothesis. The problem with this is that there are arbitrarily large polyominoes for which it is not possible to remove a domino and leave a single connected polyomino behind; in fact, there are polyominoes that cannot be split into any collection of smaller polyominoes of even size. (This is one example.)

A variant of this inductive argument that might work is to show that from any polyomino $P$, one can remove either a domino, a $T$-tetromino, or two $L$ trominoes, to leave a smaller connected polyomino. If this were true, it would suffice for the induction, but I don't see a great way to prove it. (It may well have a counterexample!)

Can every polyomino with an even number of squares be tiled by L shapes of one-third the side length?

Answer 1

Yes, I think they can. This is an outline of a proof; there may be problems in the details that I missed.

Any even polyomino with a $2\times 2$ sub-square can be cut into two pieces through the square in at least two different ways, one that leaves two odd pieces and one that leaves two even pieces. Therefore it is possible to always cut such an even polyomino into two even polyominoes.

We can continue this until have all pieces dominoes, which are tileable, or thin polyominoes, polyominoes with no such $2 \times 2$ subsquares.

If a cell in a thin polyomino has exactly two neighbors, we can again make a cut in two ways to leave either two odd or two even polyominoes, so the same trick work as before. We end up with dominoes, or polyominoes with cells that have 1, 3, or 4 neighbors (and no subsquares).

We call the ones with more than one neighbor junctions. If a polyomino has more than one junction, we can make cuts at junctions so that we break the polyomino into smaller polyominoes with more than one cell and at most one junction. The arms of these junctions (or what used to be a junction) can only be one cell (otherwise we would have a cell with two neighbors).

These polyominoes are the right tromino, T-tetromino, (and maybe not strictly necessary) the skew-tetromino and the X-pentomino, all of which are tileable by right trominoes (when scaled).

I think a similar approach can work for analyzing odd polyominoes, although it is more difficult. In addition to the scaled $1 \times k$ rectangles (for odd $k$), we can also not tile certain thin L-shapes (such as the V-pentomino scaled) and certain thin T-shapes of (such as the T-pentomino scaled) -- I have not worked through a full proof but the reason is pretty much the same as for why scaled $1 \times k$ rectangles are not tileable. My conjecture is that an odd polyomino is tileable unless it is thin, and it cannot be broken into smaller polyominoes by cuts without leaving a $1\times k$ rectangle with $k$ odd.

Answer 2

This is just a supplementary answer to Herman Tulleken's very helpful outline, since I found myself unsure of a few details and wanted to flesh out the steps a little more explicitly.

We'll demonstrate the desired result by means of a more general theorem, which we'll prove via a little casework on different substructures in the polyomino.

Theorem: Every polyomino with an even number of cells can be tiled by a combination of the following three polyominoes:

                                          

Note that since the L-tromino tiles the $3$-scaled version of all of these polyominoes, our desired result follows immediately, but this theorem could be used to prove an analogous result involving other tile shapes and scaling factors if these initial tilings exist.

---

Proof: We proceed by induction on the size of the polyomino; the base case $n=2$ is immediate.

Now, let $P$ be our polyomino of even size; we wish to decompose $P$ into smaller even-sized polyominoes and/or tiles from our base set.

Case 1: $P$ contains a $2\times 2$ square.

Fix one such $2\times 2$ square $S$. We'll look at the portions of $P$ which attach to $S$ on each side; these form some number of edge-connected components when $S$ is removed. Call each such component a branch (though note that a branch may attach to $S$ along two different sides). A given side of $S$ connects to at most one branch.

Note that if any branch $B$ is of even size, then $B$ and $P\setminus B$ are both smaller even polyominoes, so we're done. We can thus assume that all branches contain an odd number of cells, which means there are either $2$ or $4$ branches (or $0$, but then $P$ is just a $2\times 2$ square and splits into dominoes).

Case 1.1: There are two branches $B_1$ and $B_2$.

If this happens, pick a square $s\in S$ adjacent to $B_1$; our decomposition is $B_1\cup s$ and $B_2\cup(S\setminus s)$. This will only fail if $B_2$ attaches to $S$ only at square $s$ - in this case, let $D$ be a domino containing $s$, and take our decomposition to be $S\setminus D$ and $B_1\cup B_2\cup D$. This is illustrated below, with $B_1$ in red, $B_2$ in blue, $D$ in purple connecting red and blue, and the leftover domino in green.

Case 1.2: There are four branches. Note that each one must connect to exactly one side of $S$.

If any square in $s$ is connected to a single branch $B_1$, or to two branches but with $B_2$ having a second connection, then we can split into $B_1\cup s$ and $B_2\cup B_3\cup B_4\cup (S\setminus s)$.

Otherwise, we must have two opposite corners, each connected to two branches which meet the square at exactly those points. Then we can cut the square via a horizontal or vertical line to perform the desired decomposition.

Having exhausted this case, we may now turn to

Case 2: $P$ has a cell of degree $2$.

Suppose that a cell $c\in P$ has degree two, with neighbors $d_1,d_2$. Then we can split $P\setminus c$ into two polyominoes, with the $d_1$ and $d_2$ in different halves. (Take one piece to be the connected component of $P\setminus (c \cup d_2)$ containing $d_1$.)

But since $P$ has an even number of cells, $P\setminus c$ has an odd number of them, so exactly one of the resulting polyominoes has an odd number of cells; assign $c$ to that one to obtain our partition.

Case 3: $P$ is squarefree and all cells have degree $1,3,$ or $4$.

Note that in fact, no cell can have degree $4$ either, since any additional cells added to our $X$ pentomino would either create a $2\times 2$ square or would lead to a cell having degree $2$. So all cells have degree either $1$ or $3$.

If there are no degree-$3$ cells, $P$ must be a domino; this was covered in our base case. Otherwise, cut $P$ into pieces with each piece containing a degree-$3$ cell and all the leaves it connects to. Why does this partition work? Every cell is certainly included in it, so the only failure mode is if one of the resulting pieces isn't one of our base polyominoes. But it is easy to verify that given a degree-$3$ cell, the "middle" leaf can't be degree-$3$ without forming a $2\times 2$, and all possible subsets which include the "middle" leaf are congruent to one of the base tiles given above.

This concludes the proof. Please let me know if anything seems to be missing here or needs clarification!