Maths Olympiad Prep

Library / /79 of 87

Combinatorics Difficulty 7.3 National Olympiad, round 2 Prove it Serbia

Problem:

Let aa and bb be odd natural numbers greater than 1. Consider an a×ba \times b board which is missing the fields (2,1),(a2,b)(2,1),(a-2, b) and (a,b)(a, b) (by field (i,j)(i, j) we mean the field at the intersection of row ii and column jj). Suppose that such a board is tiled using 2×12 \times 1 dominoes and 2×22 \times 2 squares (dominoes may be rotated).
Prove that at least 32(a+b)6\frac{3}{2}(a+b)-6 dominoes are used. (Nikola Petrović)

Solution

Solution:

Let us write into field (i,j)(i, j) the number (1)i+j(i+j)(-1)^{i+j}(i+j). The sum of the written numbers over the whole board is i=1a(1)ij=1b(1)j(i+j)=i=1a(1)i+1(i+b+12)=a+b+22\sum_{i=1}^{a}(-1)^{i} \sum_{j=1}^{b}(-1)^{j}(i+j)=\sum_{i=1}^{a}(-1)^{i+1}\left(i+\frac{b+1}{2}\right)=\frac{a+b+2}{2}, and if the three mentioned fields are removed, the sum over the remainder of the board is
a+b+22(3)(a+b2)(a+b)=32(a+b)+6 \frac{a+b+2}{2}-(-3)-(a+b-2)-(a+b)=-\frac{3}{2}(a+b)+6
Since the sum of the numbers in every 2×22 \times 2 square is equal to zero, and the sum in every domino is 1 or -1, at least 32(a+b)6\frac{3}{2}(a+b)-6 dominoes are needed.

Second solution. Let the rows and columns be numbered from bottom to top and from left to right. We may assume that none of the configurations marked LL in the figure occurs in the tiling - indeed, they can be replaced by the corresponding configurations marked DD, without increasing the number of dominoes.
Consider the piece that covers field (a,1)(a, 1). If it is, say, the horizontal domino (a,1)(a,2)(a, 1)-(a, 2) (the case of a vertical domino is examined analogously), then field (a1,1)(a-1,1) cannot be covered either by a square or by a horizontal domino (since together with the domino above they would form one of the configurations LL), so it must be covered by the vertical domino (a1,1)(a2,1)(a-1,1)-(a-2,1). Similarly, now field (a1,2)(a-1,2) must be covered by the domino (a1,2)(a1,3)(a-1,2)-(a-1,3), and so on indefinitely, which is impossible. Therefore, the piece that covers field (a,1)(a, 1) is a square.
In a similar way, fields (a,3)(a, 3) and (a2,1)(a-2,1) are also covered by squares, then fields (a,5),(a2,3)(a, 5),(a-2,3) and (a4,1)(a-4,1), and so on. Continuing this process, we conclude that all fields except those in rows 1,2,31,2,3 and those in columns b2,b1,bb-2, b-1, b are covered by squares. The remaining fields can be tiled in a unique way, shown in the figure, which is checked directly. In doing so, exactly 32(a+b)6\frac{3}{2}(a+b)-6 dominoes are used.

Figure 1

Third solution. Let us color the fields of the board black and white as on a chessboard. We call the line separating the ii-th and (i+1)(i+1)-th row/column the ii-th horizontal/vertical.
If jj is even (2jb12 \leqslant j \leqslant b-1), at least one (horizontal) domino crosses the jj-th vertical, because the number of fields in the first jj columns is odd. On the other hand, if jj is odd (1jb2)(1 \leqslant j \leqslant b-2), at least two dominoes must cross the jj-th vertical, because in the first jj columns there are two more black fields than white fields. This way we obtain at least 3b32\frac{3b-3}{2} horizontal dominoes.
Similarly, if ii is even (2ia3)2 \leqslant i \leqslant a-3) or i{1,a2}i \in\{1, a-2\}, at least one (vertical) domino crosses the ii-th horizontal, because the number of fields in the first ii rows is odd. On the other hand, if ii is odd (3ia43 \leqslant i \leqslant a-4), the number of black fields in the first ii rows is two greater than the number of white fields, so at least two dominoes must cross the ii-th horizontal. This way we obtain at least 3a92\frac{3a-9}{2} vertical dominoes.
Thus, in total there are at least 3a92+3b32=32(a+b)6\frac{3a-9}{2}+\frac{3b-3}{2}=\frac{3}{2}(a+b)-6 dominoes.

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 translated into English from sr; metadata (topic, difficulty) added by this project.