Each unit square in a 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.
Solutions — 2
Solution 1
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.
Solution 2
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.
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.