Maths Olympiad Prep

Library / /9 of 24

Combinatorics Difficulty 6.1 National olympiad Prove it Argentina

Each cell in an 8×88 \times 8 board is painted white or black, in such a way that every 2×32 \times 3 or 3×23 \times 2 rectangle contains at least two black cells having a common edge. What is the minimum number of black cells that there can be in the board?

Solution

We claim that at least two of the cells A,B,C,DA, B, C, D in a block as in the picture are black.
Figure 1
Otherwise, there are at most one black cell among them; then, there are at least 3 white cells. Without loss of generality, assume that A,B,CA, B, C are white. Then, the following 2×32 \times 3 rectangle does not have two black cells with an edge in common, which is a contradiction:
Figure 2
Now, consider the following 6 groups of cells:
Figure 3
Each of these groups contains at least 2 black cells; then, the board has at least 12 black cells among them. In addition, by symmetry, there are at least 12 black cells among the remaining ones. Therefore, the number of black cells is the board is greater than or equal to 24.
The following is an example with 24 black cells:
Figure 4
We conclude that the minimum number of black cells that the board can have is 24.

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.