Tiling a 7x9 rectangle with 2x2 squares and L-shaped trominos

It's possible to cover a 7x9 rectangle using 0 2x2 squares and 21 L-shaped trominos, for example:

abbcddeef
aabccdeff
gghiijjkk
glhhimjnk
lloppmmnn
qoorpstuu


It's also possible to cover it with 3 2x2 squares and 17 L-shaped trominos, for example:

aabbccdee
fagbcddee
ffgghhijj
kkllhhiij
kklmmnnoo
ppqrmsnot


However, it is not possible to use more than 3 2x2 squares, that is, the remaining four combinations don't work:

• 6 2x2 squares and 13 L-shaped trominos
• 9 2x2 squares and 9 L-shaped trominos
• 12 2x2 squares and 5 L-shaped trominos
• 15 2x2 squares and 1 L-shaped tromino

...at least this what I got using brute force (a simple C program based on backtracking). I tried to give a mathematical proof for this, but I couldn't.

• What's the question? – Lord Shark the Unknown Jan 4 at 19:29
• @LordSharktheUnknown The question is, how can this claim be proved? – user80827 Jan 4 at 19:31
• What's "the normal way" to prove this that you refer to? – Michael Lugo Jan 4 at 20:14
• @MichaelLugo I would like to find a mathematical proof, because I don't like computer based proofs. My C code tried every possible way to find a tiling with a given number of 2x2 squares and L-trominos, but it does not tell anything about why one cannot use more than 3 2x2 squares. – user80827 Jan 4 at 20:20
• Tile homology groups can be useful for these types of questions. cflmath.com/Research/Tilehomotopy/tilehomotopy.pdf – Cheerful Parsnip Jan 5 at 2:17

This answer (to a different tiling problem) gave me the idea to use more than 2 colors to color the 7x9 rectangle (I have already tried the chessboard coloring without any success).

I devised a coloring scheme with which every 2x2 square always covers the same number of fields for each color, independently of its position. This can be achieved using 3 colors (say, a, b and c):

ababababa
bcbcbcbcb
ababababa
bcbcbcbcb
ababababa
bcbcbcbcb
ababababa


The number of fields per color: $$a = 20, b = 31, c = 12$$.

Every 2x2 square covers 1 a-, 2 b- and 1 c-fields. Let $$S$$ denote the total number of 2x2 squares.

There are 3 groups of L-shaped trominos:

• Group-1 trominos cover 1 a-, 1 b- and 1 c-fields.
• Group-2 trominos cover 1 a-, 2 b- and 0 c-fields.
• Group-3 trominos cover 0 a-, 2 b- and 1 c-fields.

Let $$L$$, $$L_1$$, $$L_2$$ and $$L_3$$ denote the total number of L-trominos, and the number of trominos in each group, respectively. The following equations hold:

\begin{align} L_1 + L_2 & = a - S \\ L_1 + 2L_2 + 2L_3 & = b - 2S \\ L_1 + L_3 & = c - S \end{align}

(Note: The summation of these equations gives

\begin{align} 3(L_1 + L_2 + L_3) & = a + b + c - 4S \\ 3L + 4S & = a + b + c \\ 3L + 4S & = 63 \; (= 7 \cdot 9) \end{align}

as expected.)

The solution for the above system of equations:

\begin{align} L_1 & = \frac{2a - b + 2c - 2S}{3} = 11 - \frac{2S}{3} \\ L_2 & = \frac{a + b - 2c - S}{3} = 9 - \frac{S}{3} \\ L_3 & = \frac{-2a + b + c - S}{3} = 1 - \frac{S}{3} \end{align}

It's already mentioned in the question that the only possible values for $$S$$ are 0, 3, 6, 9, 12 and 15. Substituting these values into the expressions for $$L_1$$, $$L_2$$ and $$L_3$$ shows that while both $$L_1$$ and $$L_2$$ are positive for all $$S$$ values, $$L_3$$ becomes negative for $$S > 3$$, which means that our tiling problem cannot be solved using more than 3 2x2 squares.

• The calculations are even simpler if 4 colors are used: abab... on the 1st line, cdcd... on the 2nd line, etc. In this case, there are 4 tromino groups, and similarly to the 3-color case, the size of one group becomes negative for $S > 3$. – user80827 Jan 5 at 9:40