Maths Olympiad Prep

Library / /137 of 196

Combinatorics Difficulty 5.6 AIME, harder Prove it Soviet Union

Problem:

Some unit squares in an infinite sheet of squared paper are colored red so that every 2×32 \times 3 and 3×23 \times 2 rectangle contains exactly two red squares. How many red squares are there in a 9×119 \times 11 rectangle?

Solution

Solution:

Figure 1

There cannot be two red squares with a common side. For consider as the diagram shows we can immediately conclude that the squares with a \ast are not red, but now the bold rectangle has at most 1 red square. Contradiction.

Figure 2

Consider a red square. One of the two diagonally adjacent squares marked \ast must be red. But it is now easy to show that all red squares on that diagonal are red and that the other red squares are those on every third parallel diagonal line. Any 9×119 \times 11 rectangle must have just three such diagonals on a 9 cell border row, and hence just 3 red cells in that border row. But the remaining 9×109 \times 10 rectangle can easily be partitioned into fifteen 3×23 \times 2 rectangles, each with 2 red squares.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.