Proof. Let \(t\) be the number of colors.

Consider the band \([t+1] \times \mathbb{Z}\). In each row of the band we must have two points of the same color, a “monochromatic line segment”. We can identify the monochromatic line segments by their location, for which there are \(\binom{t+1}{2}\) options, and it’s color, of which there are \(t\) options.

Thus, if we look at \((t+1)t^2 / 2 + 1\) rows of the band we will find two that have the same color and location. This is a monochromatic axis aligned rectangle.