Balkan Mathematical Olympiad

(1) Consider the graph $G$ whose vertices are the board's cells and whose edges are all pairs of neighbouring (i.e., having a common side) cells coloured in different colours. We wish to show that $G$ contains a simple path of length at least $n$.

(2) On a new $n\times n$ chessboard $B$, colour each connected component in $G$ in its own colour. (So that two cells $u$ and $v$ are coloured in the same colour exactly when there is a path from $u$ to $v$ in $G$.) Each pair of neighbouring cells which are coloured in different colours in $B$ would have to be coloured in the same colour in the original board $A$ – otherwise, a path in $G$ of length 1 would exist between them. Therefore, $B$ does not contain a $2\times 2$ square whose cells are coloured in more than two colours or a $2\times 2$ square whose cells are coloured in a checkerboard pattern: otherwise, the corresponding $2\times 2$ square in $A$ would be monochromatic. From now on, we will refer to $B$'s colouring only.

(3) Label each cell in $B$ with the coordinates of its center so that the bottom left and the top right cells are labeled $(1,1)$ and $(n,n)$, respectively. In $B$, there is at least one pair of boundary cells of the same colour. (Otherwise, all $2\times 2$ squares which contain a corner cell would contain more than two colours.) Of all such pairs, let $u=(x_u,y_u)$ and $v=(x_v,y_v)$ be the one which maximizes $d(u,v)=|x_u-x_v|+|y_u-y_v|$. We will show that $d(u,v)\ge n-1$. The claim would then follow because any path in $G$ from $u$ to $v$ would visit at least $n$ distinct cells.

(4) Suppose, by way of contradiction, that $d(u,v)<n-1$. If $u$ and $v$ lie in two opposite edge rows or two opposite edge columns, then we would have $d(u,v)\ge n-1$, a contradiction. Without loss of generality, then, $u$ and $v$ lie in the union of the leftmost column and the bottommost row. Consider the sequence $$b_1=(2,n),b_2=(1,n),b_3=(1,n-1),b_4=(1,n-2),\dots ,b_{n+1}=(1,1),$$ $$b_{n+2}=(2,1),b_{n+3}=(3,1),\dots ,b_{2n}=(n,1),b_{2n+1}=(n,2)$$ of boundary cells, and let $r$ and $s$ be the positions of $u$ and $v$ in this sequence so that $u\equiv b_r,v\equiv b_s$, and $1<r<s<2n+1$.

(5) Suppose that $u$ and $v$ are both green. It is easy to see that, if there was a green boundary cell $w$ which is not one of $b_r,b_{r+1},\dots ,b_s$, then we would have either $d(u,w)>d(u,v)$ or $d(w,v)>d(u,v)$, which is a contradiction. Therefore, all green boundary cells are contained in the set $\{b_r,b_{r+1},\dots ,b_s\}$.

(6) Suppose that $b_{r-1}$ is white. Let $p_1$ and $p_2$ be the common vertices of the cells $b_{r-1}$ and $b_r$ so that $p_1$ lies on the boundary of the board. Let $p_1,p_2,\dots ,p_k$ be a sequence of cell vertices such that, for all $i$, $p_i{p}_{i+1}$ is the common edge of a white cell and a green cell which lie to the left and to the right of the directed segment $\overrightarrow{p_i{p}_{i+1}}$, respectively. We will refer to sequences of this type as border sequences.

(7) A border sequence does not repeat vertices. Indeed, we have $p_1\ne p_2$, and if $p_k=p_l$ and $p_{k-1}\ne p_{l-1}$ for some $l<k$, then the $2\times 2$ square of center $p_k$ would have to be coloured in a checkerboard pattern, a contradiction. Let, then, $p_1,p_2,\dots ,p_k$ be the longest possible border sequence. If $p_k$ was not a boundary vertex, then the $2\times 2$ square of center $p_k$ would be coloured in white and green only, and in all permitted colourings at least one of the three vertices at a distance of 1 from $p_k$ could be added to the sequence: a contradiction. It follows that the sequence can only terminate in a boundary vertex and that the edge $p_{k-1}{p}_k$ divides a green boundary cell $g$ and a white boundary cell $w$. Since the broken line $p_1{p}_2\dots p_k$ cannot intersect the all-green path in $G$ from $b_r$ to $b_s$ and a border sequence does not repeat vertices, the cell $g$ cannot be any of $b_r,b_{r+1},\dots ,b_{s-1}$. By (5), then, $g\equiv b_s$ and, therefore, $w\equiv b_{s+1}$.

(8) We have shown that the cells $b_{r-1}$ and $b_{s+1}$ are both white. Since $d(b_r,b_s)<n-1$, then, $d(b_{r-1},b_{s+1})>d(b_r,b_s)$: a contradiction, as needed.