Kvant Math Problem 415

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 2m23s
Source on kvant.digital

Problem

What is the maximum number of kings that can be placed on a toroidal chessboard $n\times n$ so that they do not attack each other? A toroidal chessboard is obtained from a standard chessboard of size $n\times n$, in which the top and bottom ranks, as well as the left and right files, are identified (glued together). On a toroidal board, from each square a king can move to eight neighboring squares (see Fig. 2).

Fig. 2

A. Futer

Exploration

The problem asks for the maximum number of mutually non-attacking kings on an $n\times n$ toroidal board. Two squares are adjacent when their coordinates differ by $(\pm1,0)$, $(0,\pm1)$, or $(\pm1,\pm1)$ modulo $n$. Thus adjacency is taken in the graph on $\mathbb{Z}_n\times\mathbb{Z}_n$ where each vertex is connected to the eight surrounding vertices in the grid metric with wrap-around.

A $2\times2$ block forms a complete graph, since any two distinct squares in such a block differ by at most $1$ in each coordinate, hence are adjacent on the torus as well. Therefore at most one king can be placed in each $2\times2$ block.

There are $n^2$ distinct $2\times2$ blocks when blocks are indexed by their upper-left corner in $\mathbb{Z}_n\times\mathbb{Z}_n$, and each vertex belongs to exactly four such blocks. This suggests the bound $\alpha \le n^2/4$.

The main difficulty is whether this bound is always achievable on the torus, especially when $n$ is odd, where naive $2\times2$ periodic patterns conflict with wrap-around identifications.

Problem Understanding

This is a Type C problem. We must determine the maximum number of non-attacking kings on the toroidal chessboard.

The structure is a graph on $\mathbb{Z}_n^2$ with king adjacency. The goal is to compute its independence number. The natural expectation from local $2\times2$ cliques is that the answer should be $\lfloor n^2/4\rfloor$, since each $2\times2$ block can contain at most one king and a periodic construction should asymptotically achieve density $1/4$.

We aim to prove that the maximum number of kings equals

$\left\lfloor \frac{n^2}{4} \right\rfloor,$

and identify configurations achieving this value.

Proof Architecture

A first lemma establishes that every $2\times2$ subboard induces a clique of size $4$ in the king graph on the torus.

A second lemma shows that each vertex lies in exactly four distinct $2\times2$ subboards indexed cyclically on $\mathbb{Z}_n^2$.

A third lemma uses double counting of incidences between chosen vertices and $2\times2$ blocks to derive the upper bound $4|S|\le n^2$ for any independent set $S$.

A fourth lemma constructs an independent set of size $\lfloor n^2/4\rfloor$ by an explicit periodic selection of one vertex per $2\times2$ residue class, with a correction in the odd case handled by deleting a single vertex from a maximal periodic pattern.

The most delicate point is verifying that the construction remains independent under toroidal wrap-around when $n$ is odd.

Solution

Let the board be $\mathbb{Z}_n\times \mathbb{Z}_n$, and let two distinct vertices $(i,j)$ and $(i',j')$ be adjacent if and only if $\max(|i-i'|,|j-j'|)\equiv 1 \pmod n$.

For each $(i,j)\in\mathbb{Z}_n^2$, define the $2\times2$ block

$B_{i,j}={(i,j),(i+1,j),(i,j+1),(i+1,j+1)},$

with all arithmetic modulo $n$.

Each such block induces a complete graph. Indeed, for any two distinct elements of $B_{i,j}$, their coordinate differences lie in ${0,\pm1}$ in each coordinate and are not both zero, so the king move connects them on the torus.

Let $S$ be any independent set of kings. Since each $B_{i,j}$ contains at most one element of $S$, the number of pairs $(x,B_{i,j})$ with $x\in S\cap B_{i,j}$ is at most $n^2$ because there are $n^2$ blocks.

Each fixed vertex $x=(a,b)$ belongs to exactly the four blocks $B_{a,b}$, $B_{a-1,b}$, $B_{a,b-1}$, and $B_{a-1,b-1}$, with indices taken modulo $n$. Hence each vertex of $S$ contributes exactly $4$ incidences.

Double counting yields

$4|S|\le n^2,$

so every independent set satisfies

$|S|\le \frac{n^2}{4},$

hence

$|S|\le \left\lfloor \frac{n^2}{4}\right\rfloor.$

We now construct independent sets attaining this bound.

Assume first that $n=2m$ is even. Consider the set

$S={(2a,2b)\mid a,b\in\mathbb{Z}_m}.$

If two distinct elements of $S$ were adjacent, their coordinate differences would be congruent to $0$ or $\pm1$ modulo $n$. However, between two distinct points in $S$, both coordinate differences are multiples of $2$, so neither coordinate difference can be congruent to $1$ or $-1$ modulo $n$, since $n$ is even and the only residues congruent to $1$ or $-1$ are odd. This contradiction shows that $S$ is independent. Its size is $m^2=n^2/4$.

Assume now that $n=2m+1$ is odd. Consider the set

$S={(2a,2b)\mid 0\le a\le m-1,\ 0\le b\le m-1}.$

This set has size $m^2=\lfloor n^2/4\rfloor$.

We verify independence. Take two distinct elements $(2a,2b)$ and $(2a',2b')$ in $S$. Then $2a-2a'$ and $2b-2b'$ are even integers strictly between $-(n-1)$ and $n-1$. If they were adjacent on the torus, then each coordinate difference would be congruent to $0$, $1$, or $-1$ modulo $n$. Since both differences are even and $n$ is odd, the only possible congruence is $0$. Thus adjacency would force $2a\equiv 2a'\pmod n$ and $2b\equiv 2b'\pmod n$. Because $n$ is odd, multiplication by $2$ is invertible modulo $n$, so this implies $a\equiv a'\pmod n$ and $b\equiv b'\pmod n$, hence $(a,b)=(a',b')$, contradicting distinctness. Therefore $S$ is independent.

In both parity cases there exists an independent set of size $\lfloor n^2/4\rfloor$, while no independent set exceeds $n^2/4$. This proves the maximum number of non-attacking kings equals $\lfloor n^2/4\rfloor$, so the answer is

$\boxed{\left\lfloor \frac{n^2}{4}\right\rfloor}.$

Verification of Key Steps

The double counting argument relies on the fact that every vertex belongs to exactly four $2\times2$ blocks even under modular arithmetic. Each vertex $(a,b)$ appears in $B_{a,b}$, $B_{a-1,b}$, $B_{a,b-1}$, and $B_{a-1,b-1}$, and these are distinct blocks since their indices differ.

The claim that each $2\times2$ block is a clique is verified directly from the definition of king adjacency, since every pair of distinct points in such a block differs by at most $1$ in each coordinate.

In the odd case construction, the critical point is that multiplication by $2$ is invertible in $\mathbb{Z}_n$ when $n$ is odd. This ensures that no two distinct selected vertices can become congruent under toroidal wrap-around, preventing accidental adjacency created by modular identification.

Alternative Approaches

An alternative proof of the upper bound uses a coloring argument based on partitioning the torus into $2\times2$ cells and observing that any independent set intersects each cell in at most one vertex, leading again to a density bound of $1/4$. Another approach interprets the king graph as a unit-distance graph in the $\ell_\infty$ metric on $\mathbb{Z}_n^2$ and uses a tiling argument by maximal cliques. The double counting method is preferable because it remains valid without modifying the argument for different parities of $n$ and avoids delicate case analysis of wrap-around interactions.