Maths Olympiad Prep

Library / /85 of 133

, 2015

Combinatorics Difficulty 5.8 AIME, harder Prove it Saudi Arabia

We color each unit square of a 8×88 \times 8 table into green or blue such that there are aa green unit squares in each 3×33 \times 3 square and bb green unit squares in each 2×42 \times 4 rectangle. Find all possible values of (a,ba, b).

Solution

By tiling our 8×88 \times 8 table by eight 2×42 \times 4 rectangles like in Tiling (1) we find that the total number of green unit squares in the table is 8b8b.

By tiling our 8×88 \times 8 table by four 3×33 \times 3 squares, three 2×42 \times 4 rectangles and one 2×22 \times 2 square, like in Tiling (2), we find that the total number of green unit squares in the table is 4a+3b+x4a + 3b + x, where xx is the number of green unit squares in the 2×22 \times 2 square in the left upper corner. Notice that by just rotating our tiling (2) so that the 2×22 \times 2 square occupies at each time the four corners of the table, we deduce that the four 2×22 \times 2 unit squares in the four corners, all have the same number of green unit squares xx.

Finally, by tiling our 8×88 \times 8 table by six 2×42 \times 4 rectangles and four 2×22 \times 2 squares, like in Tiling (3), we find that the total number of green unit squares in the table is 6b+4x6b + 4x

Figure 1
Tiling (1)
Figure 2
Tiling (2)
Figure 3
Tiling (3)

Putting together all these totals, we obtain the relations
8b=4a+3b+x=6b+4x 8b = 4a + 3b + x = 6b + 4x
from which we deduce that b=2xb = 2x and 9x=4a9x = 4a. Since 0a90 \leq a \leq 9, either a=0a = 0 and b=0b = 0 or a=9a = 9 and b=8b = 8. In other words, either we color the whole table or we don't color at all.

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.