Maths Olympiad Prep

Library / /21 of 24

Combinatorics Difficulty 7.4 National olympiad, round 2 Prove it Belarus

An n×nn \times n (n4n \ge 4) square is divided into n2n^2 unit cells. Find all possible values of nn such that this square can be covered with some layers of 4-cell figures of the following shape [ ] (i.e. each cell of the square must be covered with the same number of these figures).
(The sides of each figure must coincide with the sides of the cells; the figures may be rotated but none of them can go beyond the bounds of the square.)
(Jury)

Solution

Answer: n=4kn = 4k, kNk \in \mathbb{N}.
If n=4kn = 4k, kNk \in \mathbb{N}, then this square can be covered with one layer (and then with any number of layers) of the figures [ ] [ ] [ ] [ ].

Let n=2m+1n = 2m + 1, m2m \ge 2. In this case we use chess coloring of the square. Suppose that the square is covered with kk layers of given figures. We write 1 and 1-1 in all black and in all white cells of the square respectively. Let B(n)B(n) and W(n)W(n) be the sums of the numbers in black and white cells of the square, respectively. Without loss of generality we can assume that B(n)>W(n)B(n) > W(n). It is evident that B(n)+W(n)=1B(n) + W(n) = 1. Now we sum up the numbers in all cells of the square so that we count each number in the cell as many times as the number of the figures covering this cell. Let SS be this sum. Since kk is the number of the figures covering each cell, we have S=k(B(n)+W(n))=kS = k(B(n) + W(n)) = k. On the other hand, any figure [ ] [ ] [ ] [ ] covers the same number of black and white cells, so the sum of the numbers in the cells covered with this figure is equal to 0. Therefore, S=0S = 0, a contradiction.
Let n=4m+2n = 4m + 2 (mNm \in \mathbb{N}). Using four colors we paint all cells of the square as it is shown in the figure (the number in the cell corresponds to the number of the color). Note that there is no cell with 4th color in the 2×22 \times 2 square in the right lower corner of the square. We place 1 in all cells painted second and third colors and place 1-1 in all remaining cells. As above we sum up the numbers in all cells of the square, then S=2kS = 2k, where kk is a number of layers. On the other hand, each figure covers exactly one cell of each color, so the sum of the numbers in the cells covered with this figure is equal to 0. Therefore, S=0S = 0, a contradiction.

Figure 1

Remark. Similar arguments can be applied for the following coloring: see Fig. 1 for n=4m+2n = 4m + 2, and Fig. 2 for n=2m+1n = 2m + 1.
Figure 2

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.