Painted Plane III solution

See the original puzzle

This puzzle requires a slightly different angle then the previous Painted Plane puzzles. We're going to use what's called the Pigeonhole Principle. The Pigeonhole Principle states that if we have more pigeons than pigeonholes, then there must exist a pigeonhole with more than one pigeon.

For example, let's say we have three points. Each one is colored either red or blue. Therefore, there must be at least two points which are the same color.

So here's the solution. Consider a grid of points, with three rows and nine columns.* In each column, there must exist two points which are the same color. Each column has 8 possible colorings, but there are 9 columns. Therefore, there must be two columns with the same coloring. Those two columns must contain a singly-colored rectangle.

*It's actually possible to prove it with only three rows and seven columns, but the proof is slightly harder to explain.

In the second problem, let's say we have N colors. We simply need to choose a larger grid of points, with N+1 rows and 2^N+1+1 columns. Each column must contain two points of the same color. Each column has 2^N+1 possible colorings. Therefore, there must exist two columns which are identically colored. Therefore, there must exist a singly-colored rectangle. Done.