[triominoes diagram] There is a square board made of at least 4 equal-sized squares. The number of squares in the board is a power of 2. An unlimited number of L-shaped triominoes are given. Each triomino is made of 3 equal-sized squares. Each equal-sized square that makes a triomino has the same dimensions as that of each equal-sized square that makes the square board.

The square board needs to be tiled with the L-shaped triominoes such that each square is covered at most once without parts of each triomino extending beyond the 3 squares it covers.

What is the minimum number of squares that can't be covered with the triominoes?



Indhu Bharathi solved this puzzle:

Answer: 1

Here is the proof:

  1. Given an n × n matrix where n is a power of 2 whose all cells except the top right corner one are filled with triominoes, it is possible to fill all cells of 2n × 2n matrix except the top right one with triominoes. Here is how to do it:
    1. Let's call the n × n matrix as N.
    2. Let's break the 2n × 2n matrix into four n × n matrices and call the bottom left one as A, the top left one as B, the top right as C and the bottom right as D.
    3. Place N in A.
    4. Rotate N clockwise 90° and place at B.
    5. Place N at C.
    6. Rotate N counterclockwise 90° and place at D.
    7. Fill the three-celled void in the center with a triominoe.
  2. 2 × 2 matrix has an obvious way to place a triominoes in such a way that the top right is empty.

From (1) and (2) it is possible to fill any n × n matrix where n is a power of 2 with triominoes in such a way that the top right cell alone is not filled.

Rajesh Balakrishnan solved this puzzle:

There will always be a minimum of one square left.

The board sizes grow in multiples of 4: 4, 16, 64, 256, etc.

22n − 1 is always divisible by 3 because 22n − 1 = (2n + 1)(2n − 1) and one of these 2 factors is a multiple of 3, as 2^n is even.

The following strategy will ensure that only one square is left out.

For convenience let's assume that the top-right square is uncovered. To get a board of the next size, 3 boards of same size are added (placed to its left, bottom, bottom-left). While placing the 3 additional boards ensure that they have their blank squares toward the bottom-left corner of the first board. Thus we will have 3 uncovered squares touching the bottom-left corner of the first board (centre of the new board) into which a triominoe can be fitted easily. So the top-right square is the only uncovered one.

David Robertson solved this puzzle:

The problem, as described on cotpi problem 20, is to fill a 2n × 2n square grid with L-shaped triominoes (which may not overlap). What is the minimum number of squares that can't be covered?

Figure 1
Figure 1: An 4 × 4 grid (n = 2) and an L-shaped triomino.

Claim   The minimum number of un-coverable squares is at most 1.

Proof. (By Induction)

Basis   Given a 2 × 2 grid, position a triomino so that:

  • It's middle square is in the lower-left corner of the grid.
  • It's two other squares are in the upper-left and lower-right corner of the grid.
Figure 2
Figure 2: 3 squares have been covered, leaving 1 uncovered square in the top-right corner.

So the minimum number of uncovered squares is either 1 or less on a 21 × 21 grid.

Hypothesis   Suppose we can cover a 2n × 2n grid with triominoes, leaving only 1 corner square uncovered. Such a covering can be rotated or reflected, to position the uncovered corner square in any corner of our choice. Without loss of generality, we choose to leave the upper-right corner uncovered.

Figure 3
Figure 3: An 8 × 8 grid has been partitioned into four 4 × 4 quadrants.

Step   Now we show that given such a 2n × 2n grid, we can construct a 2n + 1 × 2n + 1 grid with the same properties. To begin, we partition our 2n + 1 × 2n + 1 rid into four 2n × 2n quadrants (Figure 3).

Fill the lower-left and upper-right quadrants with the group of triominoes described in the hypothesis. Then place a triomino with its center square in the top-right corner of the lower-left quadrant (Figure 4).

Figure 4
Figure 4: We have filled the grid as described, covering approximately half of all squares.

Now the lower-left quadrant is completely filled. The upper-right quadrant is almost completely filled — except for the upper-right corner. We have 'overspilt' into the upper-left corner of the lower-right quadrant, and the lower-right corner of the upper-left quadrant.

However, this leaves us with two quadrants that are empty apart from one corner! We can fill the remaining space using the combination of triominoes described in the hypothesis (after reflecting them). Figure 5 illustrates this.

Figure 5
Figure 5: The remaining quadrants have been covered.

We're done! By induction, we can construct a covering of triominoes that leaves only one square uncovered for any 2n × 2n square grid. Therefore, for any grid size, the minimum number of uncovered squares is at most 1.

Corollary   The minimum number of uncovered squares is exactly 1.

Proof. We can cover some 2n square grid with only 1 uncovered square. Covering this final square would require either:

  • 2 further uncovered squares, or
  • covering 2 squares already covered by some other triomino.

Neither of these options is permitted. Therefore we cannot cover every square! So the minimum number of uncovered squares has to be exactly 1.

Alex Yeilding solved this puzzle:

The answer is 1. By induction:

Base case: n = 1: Board with 22n = 22 = 4 squares is trivially tiled, leaving the upper-right square uncovered.

Assume board with 22n squares can be tiled leaving only the upper-right corner uncovered. Then for a board with 2[2(n+1)] squares, divide it into four boards of the previously solved size, with the upper-right board oriented with its uncovered square at the upper-right corner, and the other three oriented with their uncovered squares toward the center. These three uncovered squares can be covered with one additional triomino.