MathDB

All cells of an

n\times n

table are painted in several colors so that there is no monochromatic

2\times2

square. A sequence of different cells

a_1,a_2,\ldots,a_k

is called a colorful if any two consecutive cells are adjacent and are painted in different colors. What is the largest

k{}

for which there is a colorful sequence of length

k{}

regardless of the coloring of the cells of the table?
Proposed by N. Belukhov

Problem Statement