1
$\begingroup$

The following is a Russian Mathematical Olympiad problem from 1999 (source)

Each cell of a 50×50 square is colored in one of four colors. Show that there exists a square which has cells of the same color as it directly above, directly below, directly to the left, and directly to the right of it (though not necessarily adjacent to it).

I'm curious what the minimal grid size such that the property still holds for $n$ colors is. It's pretty clear from the given proof technique that 50 is not minimal for 4 colors.

$\endgroup$
3
  • $\begingroup$ Have you worked out the minimum grid size for $4$ colors? It's greater than $8$ and at most $16$ since the given proof works for $n>16$ and it's easy to construct an $8\times8$ grid without the property. I haven't tried to go any farther. $\endgroup$
    – saulspatz
    Sep 23, 2020 at 22:55
  • $\begingroup$ The proof, slightly modified, will work for $s = 16$. (E.g The red cell with minimal $x+y$ coordinate will both be the bottom in its column and left in it's row, so it's double counted) This allows us to conclude that $s_n = n^2 $ will work. $\endgroup$
    – Calvin Lin
    Sep 23, 2020 at 23:21
  • $\begingroup$ Getting an exact minimal value seems hard to motivate, and will likely be a lot of case checking. $\endgroup$
    – Calvin Lin
    Sep 23, 2020 at 23:26

1 Answer 1

Reset to default
2
$\begingroup$

Let's consider the four color case.

If the square's dimension is $15$, then it contains $15^2 = 225 = 4\cdot 56+1$ cells and at least $57$ of these must be of the same color, say red.

Of these $57$ red squares, at most $15$ can be the uppermost (resp. lowermost; rightmost; leftmost) red squares in their columns (resp. columns; rows; rows), which gives at most $4\cdot 15 = 60$ red squares.

However, as mentioned in a comment, the uppermost (resp. uppermost; lowermost; lowermost) red square in the rightmost (resp. leftmost; rightmost; leftmost) column with a red square is both the uppermost (resp. uppermost; lowermost; lowermost) of its column and the rightmost (resp. leftmost; rightmost; leftmost) of its row, so its double counted. Therefore we have at most $60-4 = 56$ red squares satisfying any of the previous conditions.

It is clear that the square of dimension $15$ does not have the desired property. Surprisingly, the square of dimension $14$ does, as shown in the example below:

not a swastika

If this $X$-patterns is really optimal (I conjecture it is), the minimal grid size such that the property still holds for $n$ colors should be $4n-2$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .