Were you able to tile this? How can we be sure that this is not tileable? Can you find another unit square that, when removed from a grid, makes it non-tileable?

Question

Homi · Accepted Answer

We can use a checkerboard coloring to show if a region can be tiled by dominoes.

Step 1 — Count squares in the region

Let us first count the total number of squares in the region to be tiled. The region is a grid with 3 columns and 5 rows. The top row has 2 squares. The other four rows each have 3 squares. So, the total number of squares is the sum of squares in each row.

$= 2 + 3 + 3 + 3 + 3$

$= 2 + (4 \times 3)$

$= 2 + 12$

$\boxed{14 \text{ squares}}$

Since each tile covers 2 squares, we would need $14 \div 2 = 7$ tiles. This is an even number, so tiling might be possible.

Diagram 1

Step 2 — Count black and white squares

Let us color the grid like a checkerboard. We can see this in the "Black and white grid" diagram. Let us count the number of black and white squares in the region. We will count the white squares first. Row 1 has 2 white squares. Row 2 has 1 white square. Row 3 has 2 white squares. Row 4 has 1 white square. Row 5 has 2 white squares. The total number of white squares is the sum of white squares in each row.

$= 2 + 1 + 2 + 1 + 2$

$\boxed{8 \text{ white squares}}$

Now, let us count the black squares. Row 1 has 0 black squares. Row 2 has 2 black squares. Row 3 has 1 black square. Row 4 has 2 black squares. Row 5 has 1 black square. The total number of black squares is the sum of black squares in each row.

$= 0 + 2 + 1 + 2 + 1$

$\boxed{6 \text{ black squares}}$

Diagram 2

Step 3 — Check for tileability

Each tile is a $1 \times 2$ or $2 \times 1$ domino. When placed on a checkerboard, each domino always covers exactly one black square and one white square. For a region to be tileable by these dominoes, it must have an equal number of black and white squares. In our region, we found 8 white squares and 6 black squares. The number of white squares is not equal to the number of black squares. So, the region cannot be tiled.

Step 4 — Find another non-tileable removal

Let us consider a full $5 \times 3$ grid. We will color it like a checkerboard, starting with white at the top-left corner. Let's count the black and white squares in a full $5 \times 3$ grid. Rows 1, 3, 5 each have 2 white and 1 black square. Rows 2, 4 each have 1 white and 2 black squares. Total white squares = $2+1+2+1+2 = \mathbf{8}$ . Total black squares = $1+2+1+2+1 = \mathbf{7}$ . The full $5 \times 3$ grid has 8 white squares and 7 black squares. The total number of squares is $8+7=15$ . Since 15 is an odd number, a full $5 \times 3$ grid cannot be tiled by dominoes.

The question asks to remove one unit square from a $5 \times 3$ grid. After removing one square, the remaining number of squares will be $15 - 1 = 14$ . This is an even number. For the remaining region to be non-tileable, the number of black and white squares must be unequal. If we remove a white square: Remaining white squares = $8 - 1 = 7$ . Remaining black squares = $7$ . The counts are equal, so it might be tileable. If we remove a black square: Remaining white squares = $8$ . Remaining black squares = $7 - 1 = 6$ . The counts are unequal, so it will be non-tileable.

The original problem's region was a $5 \times 3$ grid with the top-middle square (1,2) removed. This square is black. So, we need to choose another black square to remove. Let's choose the square at position (2,1), which is the first square in the second row. This square is black. If we remove the square at (2,1) from the $5 \times 3$ grid: The number of white squares remains 8. The number of black squares becomes $7 - 1 = 6$ . Since 8 is not equal to 6, this new region is non-tileable.

Answer

(i) No, we were not able to tile this region. (ii) We can be sure it is not tileable because a checkerboard coloring shows 8 white squares and 6 black squares. Each tile covers one white and one black square. Since the number of white squares is not equal to the number of black squares, the region cannot be tiled. (iii) Removing the square at position (2,1) (second row, first column) from a $5 \times 3$ grid makes it non-tileable.

Question 44

Answer

More questions in IT