Coloring a narrow chess board (4x82) with four colors

Solution 1:

There are $3^4=81$ possible columns, such as $\begin{bmatrix} r & b & b & g \end{bmatrix}^T$. Since there's $4$ rows but only $3$ colors (and $3<4$), ...

... in every possible column, a color appears twice.

And since $82>81$...

... some column appears twice.

Thus there is a monochromatic rectangle.

I'm guessing the above is the desired proof, but it is possible to prove it for $4 \times 39$ rectangles.

There's a color in row 1 which occurs at least $\lceil 39/3 \rceil = 13$ times; call it red. Delete all but these $13$ columns (with a red in row $1$).

Now red only appears once in row 2 (or there's a red rectangle). Thus there's a color in row 2 which occurs at least $\lceil (13-1)/2 \rceil = 6$ times; call it green. Delete all but these $6$ columns (with a red in row $1$ and a green in row $2$).

Now both red and green only appear once in row 3 (or there's a red or green rectangle). Thus the color blue appears $6-2=4$ times in row $3$. Delete all but these $4$ columns (with a red in row $1$, a green in row $2$, and a blue in row $3$).

Since there's three colors, two of these $4$ columns must be the same, and we get a monochromatic rectangle.

Solution 2:

To force a monochromatic rectangle, a board of size

$4$ x $19$

is required (much less than $4$ x $82$).

Proof: suppose there is no monochromatic rectangle in a $4$ x $x$ rectangle.

Therefore: at most one column can contain red in both the first and the second rows.

There are $3$ colours and $C(4,2) = 6$ pairs of rows, which means there are $18$ statements of this general form. But every column must contain at least one monochromatic pair of squares!

So $x \le 18$.

By the pigeonhole principle:

a $19th$ column will force a monochromatic rectangle.