Maths Olympiad Prep

Library / /32 of 61

Combinatorics Difficulty 6.3 National olympiad Prove it Belarus

Three n×nn \times n squares form the figure Φ\Phi on the checkered plane as

Figure 1

shown on the picture. (Neighboring squares are touching along the segment of length 11).
Find all n>1n > 1 for which the figure Φ\Phi can be covered with tiles 1×31 \times 3 and 3×13 \times 1 without overlapping.

Solution

Answer: n=3kn = 3k, n=3k+1n = 3k + 1.
It is clear that any rectangle with one of the sides divided by 33 can be covered with tiles. Therefore, if n=3kn = 3k, each of the three squares and the entire figure can be tiled.

We prove that Φ\Phi can be covered for any nn of the form 3k+13k+1. Put two horizontal tiles so that each of them closes two cells in the central and one in the side square. Then each of the side squares can be divided into rectangles (3k+1)×3k(3k+1) \times 3k and 3k×13k \times 1 each of which can be tiled. The unoccupied part of the central square can be divided into rectangles of sizes 3k×23k \times 2, (3k+1)×(3k3)(3k+1) \times (3k-3) and 2×3k2 \times 3k, each of which can be tiled.

Suppose that for some n=3k+2n = 3k+2 the figure Φ\Phi was covered with tiles. Since each square contains n2=3(3k2+4k+1)+1n^2 = 3(3k^2 + 4k + 1) + 1 cells, and two adjacent squares can have only one tile in common (intersecting both of them), the tiles entirely contained in the upper square cover it all, except for the right lower cell only. Paint the cells of the upper square in three colors as shown in the figure. It is easy to see that each tile covers one square of each color so the number of cells is the same for each color. But the number of cells of color 22 is one more than the number of cells of color 11, a contradiction.

12312312
23123123
31231231
12312312
23123123
31231231
12312312
2312312

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.