Four colored dots on a graph How do you prove the following:
Suppose that every point in the plane is colored either black, white, or violet. Prove that (no matter how
the colors are distributed) I can draw a rectangle in the plane so that all four corners of the rectangle have
the same color.
with the pigeonhole principle?
 A: There’s an even slicker solution at this link, and here’s a proof using the same idea.
For each $y$-coordinate, look at the pattern of colors at $(0,y)$, $(1,y)$, $(2,y)$, and $(3,y)$. There are only finitely many $4$-point patterns, so by the pigeonhole principle, two different $y$ values, $y_1$ and $y_2$, have the same pattern of colors at $x$-values $0$, $1$, $2$, and $3$.
Using the pigeonhole principle again, one of the three colors must appear at two different $x$-values in this matching pattern of colors. Call them $x_1$ and $x_2$.
Then the four points $(x_i,y_i)$ for $i\in\{1,2\}$ are then colored the same, and those four points also form a rectangle.

A: First note that you can get arbitrarily many points of the same color on one line. Without loss of generality, say you have a vertical line with $8$ black points on it. Let these points be $\{(x,c_1),(x,c_2),\dots,(x,c_{8})\}$, with $c_i\neq c_j$ if $i\neq j$. Now consider the points $\{(x+1,c_1),(x+1,c_2),\dots,(x+1,c_{8})\}$. If two of these points are black, then we have a black rectangle and are done. Otherwise, there are $7$ points that aren't black. There are two other colors, so by the pidgeonhole principle there are $4$ that have the same color. Let them be white. So the points $\{(x+1,c_{i_1}),\dots,(x+1,c_{i_4})\}$ are white. Consider the sets 
$$S_2=\{(x+2,c_{i_1}),\dots,(x+2,c_{i_4})\}, S_3=\{(x+3,c_{i_1}),\dots,(x+3,c_{i_4})\},\dots,   S_8\{(x+8,c_{i_1}),\dots,(x+8,c_{i_4})\}.$$
If any of the sets $S_j$ have two points that are both black or both white, then you will be able to find a rectangle of that color. Otherwise, each set has two violet points. For each set, there are $\binom{4}{2}=6$ ways of choosing the $y$ coordinates of the violet points. Since there are 7 sets, by the pidgeonhole principle there will be at least two sets in which there are violet points with the same $y$ coordinates. This will give us a violet rectangle as desired. 
