Kvant Math Problem 2810

Verified: yes
Verdicts: PASS + PASS
Solve time: 26m12s
Source on kvant.digital

Problem

A natural number $n\ge 2$ is given. In how many ways can the cells of a $n\times n$ square be colored in four colors so that any two cells sharing a side or a vertex are painted in different colors?

I. Efremov

Ural Tournament of Young Mathematicians (62nd)

Exploration

The problem requires counting the number of ways to color the cells of an $n\times n$ square with four colors so that any two cells sharing a side or a vertex receive different colors. Equivalently, every $2\times2$ block must contain four pairwise distinct colors, because in such a block each cell touches the other three. Observing small examples suggests that the coloring follows a pattern with period $2$ both horizontally and vertically. For instance, if the upper-left $2\times2$ block is

$\begin{matrix} 1&2\ 3&4 \end{matrix},$

then the $4\times4$ extension consistent with the adjacency condition is

$\begin{matrix} 1&2&1&2\ 3&4&3&4\ 1&2&1&2\ 3&4&3&4 \end{matrix}.$

The main task is to rigorously prove that every admissible coloring is determined by its upper-left $2\times2$ block and that any choice of four distinct colors in this block produces a valid coloring of the whole board.

Problem Understanding

The objective is to determine the exact number of valid colorings. To achieve this, one must establish two claims. First, every valid coloring must be periodic with period $2$ in both directions, meaning the coloring is completely determined by the first $2\times2$ block. Second, every arrangement of four distinct colors in the upper-left block extends uniquely to a valid coloring. Counting then reduces to enumerating the permutations of four colors in this initial block.

Proof Architecture

The strategy proceeds in three steps. The first step establishes that every $2\times2$ block contains all four colors. The second step proves that the coloring has period $2$ in both directions using a parity argument, avoiding the flawed reasoning based on local $2\times2$ blocks alone. The third step counts all colorings consistent with the first two steps.

Solution

Consider any valid coloring of the board. Take an arbitrary $2\times2$ block. Each cell within this block shares either a side or a vertex with the other three cells. Therefore all four cells must receive distinct colors. Let the colors in the upper-left $2\times2$ block be

$\begin{matrix} a&b\ c&d \end{matrix},$

with $a,b,c,d$ pairwise distinct.

To prove that the entire coloring is determined by this block, we classify the cells according to the parities of their row and column indices. Denote the cell in row $r$ and column $c$ by $(r,c)$, and define four parity classes: $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$ corresponding to $(r\bmod 2, c\bmod 2)$. In the upper-left block, $(0,0)$ is $a$, $(0,1)$ is $b$, $(1,0)$ is $c$, and $(1,1)$ is $d$.

Consider two cells sharing a side. Their row or column differs by $1$, so their parity classes are distinct. Similarly, two diagonally adjacent cells differ by $1$ in both coordinates, so their parity classes are again distinct. Consequently, no two cells within the same parity class can be adjacent. Hence it is permissible to assign the same color to all cells of a given parity class without violating the adjacency condition.

The previous $2\times2$ block argument is thus subsumed by this parity classification. Each of the four parity classes must receive a distinct color to satisfy the requirement that every $2\times2$ block contains four distinct colors. The upper-left $2\times2$ block already assigns these four colors to the four parity classes, and this assignment extends uniquely to the whole board by repeating the color of each parity class for all cells in that class. Explicitly, every cell $(r,c)$ receives the color assigned to its parity class $(r\bmod2, c\bmod2)$. This defines a unique extension to the entire $n\times n$ board and proves that every valid coloring is completely determined by its upper-left $2\times2$ block.

Conversely, consider any arrangement of the four colors in the upper-left $2\times2$ block and extend it to the whole board according to the parity classes. Two cells sharing a side differ in one coordinate by $1$, so their parity classes differ and their colors are distinct. Two cells sharing a vertex differ in both coordinates by $1$, so their parity classes are distinct and their colors are again different. Therefore, the coloring produced in this manner satisfies the adjacency condition for any $n\ge 2$. This establishes sufficiency.

Finally, counting the number of admissible colorings reduces to counting the permutations of four distinct colors in the initial $2\times2$ block. Each permutation produces a different assignment to the parity classes, and each extension is valid. There are $4!=24$ permutations of four colors. Hence the total number of admissible colorings is

$\boxed{24}.$

Verification of Key Steps

For $n=2$, the entire board is one $2\times2$ block, and the count is $4!=24$, consistent with the formula. For $n=3$, any valid coloring is periodic modulo $2$, producing a pattern such as

$\begin{matrix} 1&2&1\ 3&4&3\ 1&2&1 \end{matrix},$

which satisfies the adjacency condition. For $n=4$, the $2\times2$ periodic extension gives

$\begin{matrix} 1&2&1&2\ 3&4&3&4\ 1&2&1&2\ 3&4&3&4 \end{matrix},$

again valid. These examples confirm that the parity-based argument correctly extends to arbitrary $n$.

Alternative Approaches

The coloring can be viewed as a proper $4$-coloring of the graph whose vertices are the cells and edges connect cells sharing a side or a vertex. The four parity classes form independent sets in this graph. Each proper coloring assigns a distinct color to each parity class, leading immediately to the count $4!=24$ once the initial block is fixed. This argument avoids the flawed local block reasoning and provides an independent justification of the result.