3
$\begingroup$

Can't figure out how does rectangle appear. Trying to sketch it.

In 4x82 chess board every square is coloured red, bue, or green. Show that no matter how the chess is coloured, there are four squares with the same color, which make a rectangle.

$\endgroup$
  • 1
    $\begingroup$ Some quick thoughts suggests that this holds true for chess boards of widths much smaller than $82$. Is there a typo in the question? Also: If you don't write anything about what you tried yourself and/or how you think the problem should be hanled you're unlikely to get much help. $\endgroup$ – Henrik supports the community Apr 28 '18 at 13:37
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

The number of columns needed is much less than $82$.

A $4$ x $19$ board

is sufficient to force a monochromatic rectangle.

Suppose there is no monochromatic rectangle. Statement: at most one column can contain e.g. $red$ in the first two rows. There are $3$ colours and $C(4,2) = 6$ pairs of rows, which means there $18$ correct statements of this kind. But every column contains at least one monochromatic pair of squares! So there are a maximum of $18$ columns.

By the pigeonhole principle,

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.