Maths Olympiad Prep

Library / /23 of 24

Combinatorics Difficulty 7.4 National olympiad, round 2 Prove it Argentina

A 27×2727 \times 27 square board is given. Carla paints some of the cells of the board in blue, so that at least one cell remains unpainted and the following two conditions hold simultaneously:

* In every 2×22 \times 2 sub-board, the number of blue cells is even.
* In every 3×33 \times 3 sub-board, the number of blue cells is odd.

Determine the maximum number of cells that Carla can paint.

Solution

We will first show that in a valid coloring of the board there cannot be a 3×33 \times 3 sub-board with all its cells painted in blue.

Consider an n×nn \times n sub-board TT with all cells painted in blue, for the maximum nn, and assume n3n \ge 3. Since the board has unpainted cells, we may find an (n+1)×(n+1)(n+1) \times (n+1) sub-board QQ containing TT. Without loss of generality, we may assume TT is in the upper-left corner of QQ, as in the following picture:

Figure 1

We look at the nn cells to the left of TT; we call them c1,c2,,cnc_1, c_2, \dots, c_n, from top to bottom. Note that, given two adjacent cells cic_i and ci+1c_{i+1}, there cannot be one painted and the other unpainted, since in this case, the 2×22 \times 2 sub-board of QQ containing them would have exactly three painted cells (two cells in TT and one in the last column). We deduce that the cells c1,,cnc_1, \dots, c_n are either all painted or all unpainted. If n3n \ge 3, the former is not possible, since at least one of the cells c1,c2,c3c_1, c_2, c_3 must be painted so that the 3×33 \times 3 sub-board in the right-upper corner of QQ has an odd number of blue cells. We conclude that all the cells cic_i must be painted. Similarly, the same holds for all the cells of QQ that are below TT. Now, by looking at the 2×22 \times 2 sub-board in the bottom right corner of QQ, we deduce that the corner cell is also painted since, otherwise, this sub-board would contain exactly 3 blue cells. Summarizing, we have proved that all the cells of QQ are painted in blue, contradicting the maximality of TT. The contradiction arises from the assumption n3n \ge 3. It follows that the board cannot contain any 3×33 \times 3 board completely painted in blue.

Now consider any 3×33 \times 3 sub-board TT. By assumption, it contains an odd number of blue cells, and we have proved that this number cannot be 9. Let us show that there cannot be 7 blue cells either. If this is not the case, the two unpainted cells AA and BB belong to the same 2×22 \times 2 sub-board of TT (otherwise, a 2×22 \times 2 sub-board of TT containing AA would have 3 blue cells). Assume, with no loss of generality, that AA and BB are in the 2×22 \times 2 sub-board in the upper-left corner of TT. Then, the 5 cells of TT around this sub-board are painted:

Figure 2

But then, the cell marked with \star has to be painted so that the 2×22 \times 2 board in the bottom-right corner has an even number of blue cells. From this fact, with a similar argument, it follows that the cells marked with Δ\Delta are also painted. This contradicts the fact that TT has 2 unpainted cells.

We conclude that every 3×33 \times 3 sub-board has at most 5 blue cells. As the 27×2727 \times 27 board can be subdivided into 81 of those sub-boards, we have that Carla can paint at most 5×81=4055 \times 81 = 405 cells in blue. In the next example, in which the pattern is repeated every 3 rows and every 3 columns, every 3×33 \times 3 board has exactly 5 blue cells.

Figure 3

Therefore, the maximum number of cells that Carla can paint is 405.

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.