Red Square

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).

Click for Answer