Learn / Library / Combinatorics

Forced rectangle

CombinatoricsHard

Each cell of a grid with $3$ rows and $n$ columns is painted red or blue. A rectangle is monochromatic if its $4$ corner cells, taken from $2$ different rows and $2$ different columns, have the same color. What is the smallest $n$ such that every painting must contain a monochromatic rectangle?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Each column must contain $2$ cells of one color; label columns by which rows match and in what color.

Solution

A column has $3$ cells and $2$ colors, so some cells of the column share a color.
Label a column by a pair of its rows that match and their color; there are $3$ row pairs and $2$ colors, so $6$ labels.
If $2$ columns get the same label, the $4$ corners form a monochromatic rectangle, so $7$ columns force a repeated label.
With $6$ columns the labels can all differ, for example with the columns $RRB$ , $BBR$ , $RBR$ , $BRB$ , $BRR$ and $RBB$ , each having exactly one matching pair of cells, and no rectangle appears.
Hence the smallest $n$ is $7$ .

Answer: $7$

Next question Back to the library