Problem 1168

Solution. Let's denote the rows of the given table as $1,2,3,4,5$, and the columns as $a, b, c, d, e$, similar to the conventional notation of a chessboard (diagrams a), b), and c)). Let the colors mentioned in the problem be blue (the blue squares are the penalized ones) and red. In the first row, at least three squares are of the same color, and for definiteness, let's assume that these are the squares $a 1, b 1, c 1$ which are blue. If in any row from 2 to 5 in the first three columns there are two blue squares (for example, as in diagram a), squares $a 3$ and $b 3$), then the desired rectangle is determined.

!
a)

!

b)

!

c)

Therefore, let's assume that in each of the following four triplets

$$(a 2, b 2, c 2), \quad(a 3, b 3, c 3), \quad(a 4, b 4, c 4), \quad(a 5, b 5, c 5)$$

at least two squares are red. If in one of these triplets all squares are red (as in diagram b), this is the triplet ($a 5, b 5, c 5$)), then a monochromatic rectangle is easily determined. If in each of these four triplets there are exactly two red squares, then there are three possible arrangements of the red squares, and by the pigeonhole principle, at least in two of them the squares are

!
arranged in the same way, which again gives the desired rectangle. In diagram c), this is the rectangle $a 3, c 3, a 5, c 5$.

That the statement does not hold for a square with side 4 is shown by the diagram on the right.

## II year