Maths Olympiad Prep

Library / /16 of 16

Combinatorics Difficulty 7.8 National olympiad, round 2 Prove it Argentina

Let m,n2m, n \ge 2. You want to completely cover an m×nm \times n board without any gaps or overlaps, using only pieces of the following two types:
Figure 1
Type A

Figure 2
Type B
Each type A piece must cover exactly 4 squares on the board, and each type B piece must cover exactly 5 squares on the board. Rotating the pieces is allowed. Determine all pairs (m,n)(m, n) for which this can be done.

Solution

We will prove that the only boards that can be covered with the given pieces are the following:
* Those with both sides even.
* Those with both sides divisible by 3.
* Those with at least one side divisible by 6.

If both mm and nn are even, then the m×nm \times n board can be divided into 2×22 \times 2 squares, which can be covered using type A pieces. On the other hand, using one piece of each type, a 3×33 \times 3 square can be formed. Therefore, if both mm and nn are divisible by 3, since the m×nm \times n board can be divided into 3×33 \times 3 squares, it can be covered using the given pieces.

Now let's see that for every n2n \ge 2, a 6×n6 \times n board can be covered using the given pieces (and thus, by stacking multiple of these, any 6k×n6k \times n board can be covered, as we claim).
We can form a 6×26 \times 2 rectangle by vertically stacking three type A pieces. We can also form a 6×36 \times 3 rectangle by stacking two 3×33 \times 3 squares, which we have already seen how to form. Now, if n2n \ge 2 is even, we can form the 6×n6 \times n rectangle using multiple 6×26 \times 2 rectangles; and if nn is odd, we can first place a 6×36 \times 3 rectangle followed by enough 6×26 \times 2 rectangles. The figure shows an example for n=7n = 7.

Figure 3

We will now prove that there are no other solutions. Let's consider a board of size m×nm \times n that can be covered. If both sides are even, we have already seen how to do it. So, without loss of generality, let's assume that mm is odd. We color the cells of the board alternately by rows: the cells in the first row are black, the cells in the second row are white, the cells in the third row are black, and so on until the mm-th row, which is black (because mm is odd). We observe that in the thus colored board, there are nn more black cells than white cells. Now let's notice that each type A piece always covers 2 white cells and 2 black cells, while a type B piece can cover either 4 white cells and 1 black cell, or vice versa. Thus, in each piece, the difference between the number of white cells covered and the number of black cells covered is divisible by 3. Consequently, if the board can be covered, the total difference between white and black cells must also be divisible by 3. This difference is nn.

So far, we have shown that if one side is odd, the other side must be divisible by 3. If nn were odd, the same argument would allow us to prove that mm is divisible by 3, and we would be in a case that has already been considered. Therefore, we only need to consider the case of even nn, but then nn would be divisible by 6, which is again a case we have already analyzed. This proves that there are no other solutions apart from the three mentioned at the beginning.

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.