One Less Than Tetris

Lemma: if a corner square that is not uncovered or neighboring an uncovered square, the trimino that covers it must have it's middle square at that corner.

Proof: Assume for contradiction that there exists a covering of 15 out of the 16 squares without this property. Then there must be a trimino with first or third square at the corner. WLOG let this corner R1C1, R1C2, and R2C2. Because R1C1 is not neighboring a blank square, R2C1 must be part of a trimino, so there must be a trimino covering R2C1, R3C1, R3C2. Clearly R4C1 cannot be trimino-coverable, so it must be our sole uncovered square. This implies all other square are covered, so there is a trimino covering R4C2, R4C3, and R3C3, but then R4C4 is not coverable, a contradiction to our covering. QED

Now we can do casework on where the uncovered square is. If the uncovered square is in the corner, the diagram looks like this: (the C's are covered by the lemma) $$

X .CC

, . .C

C . .C

CCCC, so there is clearly one way.

If the uncovered square on an edge, the diagram looks like this: $\\$

. X CC $\\$

. . .C $\\$

C . .C

CCCC, so there is also clearly one way.

If the uncovered square is in the middle, the diagram looks like this:

CCCC

CX .C

C . .C

CCCC, so there is also exactly one way. Since we just proved that there is only one way (no more, no less) of tiling the square for each uncovered square, there are 16 possibilities of covering the square.

At first, the problem seems rather daunting, and it seems as if you have to actually plot out individual arrangements. A little thought shows that this is not so.

First consider, a 2x2 chessboard. There are 4 ways to tile this using a single Trimino, found simply by rotating the trimino to leave 4 different squares uncovered.

Now, consider the relevant 4x4 chessboard.

If you notice, we can split this board into quarters. Each of which becomes a 2x2 chessboard in it's own right.

Now, the uncovered square must lie in one of these quarters. Let us suppose that it lies in one of them, say, Quadrant 1. One can clearly see that for any uncovered square in this quadrant, it is impossible to use multiple triminos-partially lying in other quadrants- to tile quadrant 1. There must be just a single trimino in quadrant 1 with the remaining square uncovered, just like in our initial 2x2 chessboard.

Therefore, the question is simply a matter of tiling the remaining 3 quadrants, with 4 triminos. Due to the interesting L-shape of the Trimino, one notices that there is just 1 way to tile the remaining 12, as each of the triminos is identical.

This is a relief. The problem is solved. For, now, as there are 4 quadrants, by symmetry, each of them could be the initial quadrant with the uncovered square, and as there are 4 holes in each quadrant that could be uncovered by rotating the trimino in that quadrant, the number of ways that the 4x4 chessboard can be tiled is simply,

4x4= 16.

Let the squares of the chessboard be labeled $(x, y)$ for $x, y = 1, 2, 3, 4$ .

Lemma: If the squares $(3,3)$ , $(3,4)$ , $(4,3)$ and $(4,4)$ are removed from the chessboard, then there is exactly 1 way to cover the remaining L-shaped figure.

Proof: Of the 3 ways to cover $(1,4)$ , only the covering $(1,3)$ , $(1,4)$ , $(2,4)$ poses no immediate obstruction. The same must holds for the square $(4,1)$ . Then, there is only 1 way to cover the remaining tiles.

Now we consider the following cases:

Case 1: An inner square is uncovered. Without loss of generality we assume it is $(3,3)$ . By considering the covering of $(4,4)$ , it can only be covered by $(3,4)$ , $(4,3)$ , $(4,4)$ . Using the Lemma, there is exactly 1 way to cover the remaining tiles.

Case 2: An edge (but not corner) square is uncovered. Without loss of generality we assume it is $(3,4)$ . By considering the covering of $(4,4)$ it can only be covered by $(4,4)$ , $(3,4)$ , $(3,3)$ . Using the Lemma, there is exactly 1 way to cover the remaining tiles.

Case 3: A corner square is uncovered. Without loss of generality we assume it is $(4,4)$ . Consider the covering of $(3,3)$ . If the trimino includes $(3,4)$ but not $(4,3)$ , then $(4,3)$ has to be covered with $(4,3)$ , $(4, 2)$ , $(3,2)$ . But then $(4,1)$ can’t be covered. If the trimino doesn’t include either $(3,4)$ or $(4,3)$ , then neither of these square can be covered with a trimino. Hence, $(3,3)$ must be covered by $(4,3)$ , $(3,3)$ , $(3,4)$ . Using the Lemma, there is exactly 1 way to cover the remaining tiles.

Hence, each square can be left uncovered with exactly one configuration. Thus there are $16\times 1 = 16$ ways to leave one square uncovered.

Note: This solution doesn’t generalize for an n by n square.

Partition the 4 by 4 chessboard into four 2 by 2 sub-chessboards and label them as $I, II, III, IV$ clockwise, with $I$ as the top left sub-chessboard. Let $C$ be the common corner of the 4 sub-chessboards.

Without loss of generality, let the square to be left uncovered in the chessboard be any of the 4 squares in $I$ . We show that we can cover the 15 remaining squares with 5 triminos.

Clearly, one trimino can be used to cover the 3 other squares in $I$ .

For each of the sub-chessboards $II, III, IV$ , leave uncovered the square that touches $C$ . This way, one trimino can cover the remaining squares in each of $II, III, IV$ . But the 3 uncovered squares also form a trimino. Thus, the sub-chessboards $II, III, IV$ can be covered by 4 triminos.

(It is easy to check that this is the only way of covering $II, III, IV$ .)

We have shown that for any square we choose to leave uncovered, we have $1$ unique way to cover the remaining squares with 5 triminos. Hence, there are $16$ possible ways.

We can break the 4by4 into 4 2by2 squares, and use casework. We try to find how many ways are there to place the empty square in one of the 2by2 squares, and we can multiply that by 4 for the 4 rotations to find the answer. We find that using 4 triminos, there is one way to fill up all of the spaces except for the targeted 2 by 2. With the last trimino, you can place in 4 ways, leaving each of the spaces empty, so there are 4 ways for each 2 by 2. We multiply this by 4, 4x4=16 to get our answer.