Final Round of National Olympiad

Question

Each unit square in a 5 5 table is coloured either blue or yellow. Prove that there exists a rectangle with sides parallel to the edges of the table, such that the four unit squares in its corners have the same colour. FIGURE_0

Accepted Answer

Each row contains at least 3 squares with the same colour. Similarly, the dominating colour must be the same in at least 3 rows. W.l.o.g., suppose that the first 3 rows contain at least 3 blue squares each. If the first two rows contain two blue squares in the same columns then the desired rectangle exists. Otherwise, each column contains at least one blue square in these two rows (in Fig. 18, the blue squares are consecutive w.l.o.g.). Thus in one of the first two rows there are two blue squares that are in the same columns with the blue squares in the third row. These form the desired figure.

---

Alternative solution.

The first row contains three squares of the same colour, say, blue. If in some of the remaining four rows there are two blue squares aligned to the blue squares in the first row then the desired rectangle exists. Otherwise, each of these four rows

Figure 18

contains two yellow squares aligned with the blue squares in the first row. But two yellow squares can be placed into three columns in 3 different ways only. Thus there exist two rows where these two yellow squares are in the same columns. These squares form the desired figure.