Mfrhtyj

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!

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.