Maths Olympiad Prep

Library / /4 of 20

Combinatorics Difficulty 5.1 AIME, harder Prove it Greece

A 7×77 \times 7 square is divided into 4949 unit squares with sides parallel to those of TT. We color each of the 4949 unit squares with two colors, red and blue, so that the following two conditions are simultaneously satisfied:

(i) There are exactly 44 rows in each of which the blue squares are more than the red squares.

(ii) There are exactly 44 columns in each of which there are more red squares than blue.

From all the resulting monochromatic squares, let Π\Pi be the maximum side length of a monochromatic square. Find the maximum possible value of Π\Pi 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 2×22 \times 2 monochromatic squares in the lower left, painted red).

Figure 1

Solution

In fact, if such a square, let SS, existed, then each of the rows and columns of TT to which the sides of SS belong have at least 44 squares of the same color (let with color blue in the figure 66). This contradicts condition (ii). Therefore, for every coloring, each monochromatic square has side less or equal to 33. The number 33 is maximal, as we can see in figures 66 and 77.

Figure 2
Figure 6

Figure 3
Figure 7

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.