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