Maths Olympiad Prep

Library / /39 of 53

Combinatorics Difficulty 6.7 National olympiad Prove it China

On a 10×1010 \times 10 chessboard, some 4n4n unit square fields are chosen to form a region RR. This region RR can be tiled by nn 2×22 \times 2 squares. If RR can also be tiled by a combination of nn pieces of the following types of shapes (with rotations allowed).
Figure 1
Figure 2
Determine the minimum value of nn. (Posed by Zhu Huawei)

Solution

The answer is n=4n = 4. We call those two kinds of nonsquare tiles ducks.
First, the left-hand-side figure and the middle figure below show that n=4n = 4 works.
Figure 3
Figure 4
Figure 5

Second, we show that nn must be even. We mark the (infinite) chessboard with ×\times in the pattern indicated in the right-hand-side figure. It is easy to see that each 2×22 \times 2 covers exactly an even number of crosses (either two or four crosses) and each duck covers exactly an odd number of crosses (either one or three crosses). It follows that we must have an even number of ducks in RR, i.e. nn is even.

Third, we show that n2n \ge 2. If n=2n = 2, then RR can be tiled by two 2×22 \times 2 squares. It is clear that these two squares much share a common edge. Hence, we can have only two possibilities:

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.