![[triominoes diagram]](/files/20/tiling-with-triominoes.png)
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:
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: 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:
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: 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: 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: 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:
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.