Skip to main content
OlympiadHQ

Browse · MathNet

Print

XXVII Olimpiada Matemática Rioplatense

Argentina counting and probability

Problem

Each cell in an board is painted white or black, in such a way that every or 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?

problem


problem


problem


problem
Solution
We claim that at least two of the cells in a block as in the picture are black. Otherwise, there are at most one black cell among them; then, there are at least 3 white cells. Without loss of generality, assume that are white. Then, the following rectangle does not have two black cells with an edge in common, which is a contradiction: Now, consider the following 6 groups of cells: 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: We conclude that the minimum number of black cells that the board can have is 24.
Final answer
24

Techniques

Coloring schemes, extremal argumentsPigeonhole principle