Creating rectangles on checkerboard with three colors On a $40 \times 40$ checkerboard, prove that if red, black, and white checkers are laid down, there must be four checkers of the same color that create the corners of a rectangle.
The rectangle has sides parallel to the checkerboard.
I have no idea where to start. I think inclusion/exclusion and pigeonhole principle are key, but a push in the right direction would be huge.
 A: Some color in the first row occurs at least $\lceil 40/3 \rceil=14$ times.  By symmetry, assume the first $14$ cells of the first row are black.
In the second row, in the first $14$ cells, at most one can be black (or we get a rectangle with black vertices).  Hence there is another color that occurs in these cells at least $\lceil (14-1)/2 \rceil=7$ times.  By symmetry, assume the first $7$ cells of the second row are white.
In the third row, in the first $7$ cells, at most one can be black (or we get a rectangle with black vertices), and at most one can be white (or we get a rectangle with white vertices).  This means we have at least $5$ red cells.  By symmetry, assume the first $5$ cells of the third row are red.
In the fourth row, in the first $5$ cells, at most one can be black (or we get a rectangle with black vertices), at most one can be white (or we get a rectangle with white vertices), and at most one can be red (or we get a rectangle with red vertices).  But this is impossible, since $5>3$.

In fact, this proof only requires a $4 \times 34$ checkerboard to be valid.  This is illustrated below:

The first row must have $12$ squares of the same color (color 1).  Below those $12$ must be $6$ squares of the same color (color 2).  Below those $6$ must be $4$ squares of the same color (color 3).  Below those $4$, we must have two cells of the same color, creating a monochromatic rectangle.
