Browse · MathNet
PrintSelection Examination
Greece counting and probability
Problem
A square is divided into unit squares with sides parallel to those of . We color each of the unit squares with two colors, red and blue, so that the following two conditions are simultaneously satisfied:
(i) There are exactly rows in each of which the blue squares are more than the red squares.
(ii) There are exactly columns in each of which there are more red squares than blue.
From all the resulting monochromatic squares, let be the maximum side length of a monochromatic square. Find the maximum possible value of for all possible colorings satisfying conditions (i) and (ii).
(A square of the grid is called monochromatic if all its cells have the same color. For example, after the incomplete coloring in the adjacent figure, there are two monochromatic squares in the lower left, painted red).
(i) There are exactly rows in each of which the blue squares are more than the red squares.
(ii) There are exactly columns in each of which there are more red squares than blue.
From all the resulting monochromatic squares, let be the maximum side length of a monochromatic square. Find the maximum possible value of for all possible colorings satisfying conditions (i) and (ii).
(A square of the grid is called monochromatic if all its cells have the same color. For example, after the incomplete coloring in the adjacent figure, there are two monochromatic squares in the lower left, painted red).
Solution
In fact, if such a square, let , existed, then each of the rows and columns of to which the sides of belong have at least squares of the same color (let with color blue in the figure ). This contradicts condition (ii). Therefore, for every coloring, each monochromatic square has side less or equal to . The number is maximal, as we can see in figures and .
Figure 6
Figure 7
Figure 6
Figure 7
Final answer
3
Techniques
Coloring schemes, extremal arguments