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

Question

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
qqrrssttu

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

aabbccdee
fagbcddee
ffgghhijj
kkllhhiij
kklmmnnoo
ppqrmsnot
pqqrrsstt

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.

Please help me find a proof which explains why more than 3 2x2 squares cannot be used. Thank you for your help in advance!

Answer 1

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.