Browse · MathNet
PrintXXVII 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?




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