A problem from the 1999 Russian Mathematical Olympiad:
Each cell of a 50×50 square is colored in one of four colors. Show that there exists a square which has cells of the same color as it directly above, directly below, directly to the left, and directly to the right of it (though not necessarily adjacent to it).
|
SelectClick for Answer |
A 50×50 square contains 2500 cells. At least a quarter of these, 625 cells, must be of the same color, say red. Of these 625 red squares, at most 50 can be the uppermost red squares in their columns; at most 50 can be the lowermost red squares in their columns; at most 50 can be the leftmost red squares in their rows; and at most 50 can be the rightmost red squares in their rows. Together these make up at most 200 squares. The remaining 425 (or more) red squares have none of these distinctions, so each must have a red square directly above, directly below, directly to the left, and directly to the right of it.
From Titu Andreescu and Zuming Feng, Mathematical Olympiads 1999-2000: Problems and Solutions from Around the World, 2002.
|
