Maths Olympiad Prep

Library / /19 of 20

Combinatorics Difficulty 7.0 National olympiad, round 2 Prove it Greece

We consider a 100×100100 \times 100 square consisting of 10410^4 unit squares. We call tiles of type A the rectangular tiles 8×18 \times 1 or 1×81 \times 8 consisting of 8 unit squares. We call tiles of type B the rectangular tiles 4×24 \times 2 or 2×42 \times 4 consisting of 8 unit squares. Examine if it is possible to cover the 100×100100 \times 100 square by using NN tiles of type A and NN tiles of type B, for some positive integer NN? (The tiles must be inside the initial 100×100100 \times 100 square and not overlapping.)

Solutions — 2

Solution 1

Suppose such a coverage is possible with NN tiles of type A and with NN tiles of type B. Calculating the area of the tiles, which is 8=238 = 2^3 and of the square which is equal to 1002=2454100^2 = 2^4 \cdot 5^4, we observe that we need 54=6255^4 = 625 of tiles of type A and 625 of tiles of type B, so N=625N = 625.

We color the squares of the first row alternately with colors 1 and 2. That is, we have the coloring 1-2-1-2...
We color the squares of the second row alternately with colors 3 and 4. That is, we have the coloring 3-4-3-4...
We color the squares of the third row alternately with colors 1 and 2. That is, we have the coloring 1-2-1-2... and so on.

In this coloring the 4×24 \times 2 or 2×42 \times 4 contain two squares of each color. 8×18 \times 1 or 1×81 \times 8 contain two suits in 4 squares each. In the coverage they must be covered by an equal number of the colors 1,2,3,4 and type B cover an equal number of the colors, therefore the same must be the case for the type A. Therefore the type A must be an even number, out of place since it is 625.

Solution 2

Suppose such a coverage is possible with NN tiles of type A and with NN tiles of type B. Calculating the area of the tiles, which is 8=238 = 2^3 and of the square which is equal to 1002=2454100^2 = 2^4 \cdot 5^4, we observe that we need 54=6255^4 = 625 of tiles of type A and 625 of tiles of type B, so N=625N = 625.

We split the 8×18 \times 1 or 1×81 \times 8 type A tiles into 16×216 \times 2 or 2×162 \times 16 tiles, respectively, and the 4×24 \times 2 or 2×42 \times 4 type B tiles into 8×48 \times 4 or 4×84 \times 8 tiles, respectively, so that their center of gravity to coincide with a vertex of a 1×11 \times 1 square (as in the Figure)

We do the same with the 100×100100 \times 100 square, which turns into a 200×200200 \times 200 square.

Figure 1
Figure 10

Figure 2
Figure 11

We do the same with the 100×100100 \times 100 square, which turns into a 200×200200 \times 200 square.
We consider an orthonormal coordinate system with the center of gravity of the 200×200200 \times 200 square as the origin and the length unit of the system being the length of the small squares into which the type A and type B tiles are divided.

We notice that in any coverage of the 200×200200 \times 200 square, the coordinates of the centroid of each type B tile are even numbers. The coordinates of the center of gravity of an A-type tile either placed parallel to the xx-axis or parallel to the yy-axis have opposite parity, i.e. one is odd and the other is even. In the first case, the ordinate is an odd number and in the second coordinate.

Since the algebraic sum of the coordinates of all the centers of gravity of the covering tiles must be 0, for the covering to be possible, we should use an even number of type A tiles of each kind. Since N=625N = 625 is an odd number, such tiling is impossible.

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.