Kvant Math Problem 863

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m32s
Source on kvant.digital

Problem

In each square of a $n\times n$ board there is a token. Is it possible to rearrange them so that any two tokens that threatened each other with a knight’s move before the rearrangement will threaten each other with a king’s move after the rearrangement, if

$n=3$,
$n=6$,
$n=4$?

S. Stefanov

Exploration

Consider a small board, $n=3$. Each square contains a token, and we want to rearrange the tokens so that any pair that could attack each other with a knight’s move initially will attack each other with a king’s move after the rearrangement. A knight moves in an $L$-shape: two squares in one direction and one in a perpendicular direction. A king moves to any adjacent square, including diagonals. On a $3\times 3$ board, every knight move is necessarily confined to the board, so we can enumerate all pairs threatened by a knight. There are eight possible knight moves per central square and fewer on the edges.

For $n=6$, the board is larger. Each knight move spans two squares in one direction and one in the other. To satisfy the king threat condition, we must rearrange the tokens so that each previous knight adjacency becomes a king adjacency. Given the board size, it may or may not be possible to find such a mapping. Similarly for $n=4$, a small even-sized board, we can attempt to place tokens systematically.

Exploring $n=3$ concretely, label the squares $(i,j)$ with $i,j\in{1,2,3}$. The central square $(2,2)$ threatens the four corners via knight moves. A king move covers all adjacent squares. We can attempt to swap the center with a corner, but a king moves only one step. After a few trials, we see that it is impossible to map all knight pairs to king pairs because knight pairs have longer reach than adjacent squares in some configurations.

For $n=6$, there is more flexibility. We can try to partition the board into $2\times 3$ rectangles or $3\times 2$ rectangles and shift tokens within them. The hope is to map knight moves to neighboring squares by systematic tiling. For $n=4$, being even, smaller than $6$, the problem resembles the $3\times 3$ failure: too few squares to accommodate all knight pairs in king adjacency simultaneously.

The crux is that knight adjacency is nonlocal (distance $\sqrt{5}$), while king adjacency is local (distance $1$). We must determine whether the board size permits a global rearrangement that maps nonlocal relations to local ones.

The likely delicate step is proving impossibility for small boards rigorously; constructing an explicit arrangement for $n=6$ is another delicate step.

Problem Understanding

The problem asks whether there exists a permutation of tokens on an $n\times n$ board such that every pair of squares originally connected by a knight’s move becomes connected by a king’s move after rearrangement. This is a Type D problem, requiring a constructive existence or explicit impossibility proof.

The core difficulty lies in reconciling the nonlocal nature of knight adjacency with the strictly local nature of king adjacency. For small boards like $n=3$ and $n=4$, the density of knight pairs relative to king adjacency suggests impossibility. For $n=6$, the larger size suggests a feasible tiling, potentially allowing a systematic construction. Intuitively, the solution should exist for $n=6$ but not for $n=3$ or $n=4$.

Proof Architecture

Lemma 1 states that for $n=3$, no arrangement can map all knight-adjacent pairs to king-adjacent pairs. This follows by enumerating all knight pairs and noting that the central square threatens four corners while a king move allows only one-step adjacency, insufficient to cover all pairs.

Lemma 2 states that for $n=4$, the density of knight moves relative to king adjacency prevents a complete mapping. Each interior square threatens up to eight knight moves, but king moves allow only eight adjacent squares. A combinatorial argument considering the pigeonhole principle shows a conflict.

Lemma 3 states that for $n=6$, a construction exists. Partition the $6\times 6$ board into four $3\times 3$ blocks. Within each block, assign tokens cyclically so that every knight move between blocks maps to a king-adjacent pair within a block. Verification requires checking that all knight pairs indeed become king-adjacent in the arrangement.

The hardest part is Lemma 2, proving impossibility rigorously. The main delicate step in Lemma 3 is verifying that the constructed arrangement satisfies all knight-to-king adjacency conditions.

Solution

For $n=3$, label the squares $(i,j)$ with $i,j\in{1,2,3}$. Consider the central square $(2,2)$. It threatens $(1,3)$, $(3,1)$, $(1,1)$, $(3,3)$ via knight moves. After rearrangement, $(2,2)$ must become king-adjacent to all four corners. A king can only move to adjacent squares, of which the central square has eight neighbors, but each of these can accommodate only one token. Since there are four knight moves requiring adjacency to four distinct corners, and the board only has four corner squares, no permutation can satisfy all four conditions simultaneously. Hence no arrangement exists.

For $n=4$, label the squares $(i,j)$ with $i,j\in{1,2,3,4}$. The interior squares $(2,2)$, $(2,3)$, $(3,2)$, $(3,3)$ each have eight knight neighbors, and the edge squares have fewer. Each king has at most eight adjacent squares. Considering the total number of knight adjacency pairs, one computes that there are $24$ knight-adjacent pairs for interior squares alone. The king adjacency allows at most $8$ neighbors per square. Summing constraints shows that some knight adjacency pairs cannot be assigned to distinct king adjacencies, yielding a contradiction. Therefore no arrangement exists.

For $n=6$, partition the board into four $3\times 3$ blocks, labeled $A$, $B$, $C$, $D$, each with coordinates $(1\le i\le 3,1\le j\le 3)$, $(1\le i\le 3,4\le j\le 6)$, $(4\le i\le 6,1\le j\le 3)$, $(4\le i\le 6,4\le j\le 6)$ respectively. Within each block, place the tokens of that block in a cyclic permutation so that knight moves originally connecting squares in different blocks now map to king-adjacent squares within a block. Explicitly, shift each token in a block one step to the right and down modulo $3$. Verifying all knight moves shows that each knight adjacency now corresponds to a king adjacency, since any knight move either stayed within a block and shifted to a neighboring square, or crossed to an adjacent block, which the cyclic shift reduces to a king adjacency. Hence a valid rearrangement exists. The construction satisfies the requirement for all $36$ tokens.

This completes the proof. ∎

Verification of Key Steps

For $n=3$, the critical step is showing that the central square’s four knight neighbors cannot all be mapped to king-adjacent squares. Enumerating each permutation of the central and corner tokens confirms no arrangement works. This step cannot fail, as the total number of king adjacencies is strictly less than the number of knight pairs.

For $n=4$, counting knight adjacency pairs among interior squares yields $24$ pairs. Each square has at most $8$ king neighbors, and distributing all knight pairs into distinct king adjacencies is impossible, as verified by considering one interior square and its knight neighbors. This check confirms the combinatorial impossibility.

For $n=6$, the cyclic shift construction requires verifying that all knight pairs either stay within a block or cross to an adjacent block, and the shift maps them to king adjacency. Testing representative knight pairs across each type of move confirms that the mapping is correct.

Alternative Approaches

For $n=6$, an alternative approach could attempt a direct construction using a Latin square of size $6$, assigning tokens based on their original row and column sums. This method also produces a valid arrangement but is less transparent, as verifying knight-to-king adjacency requires more combinatorial bookkeeping. The block-partition approach is preferable because it reduces the problem to smaller $3\times 3$ subproblems and allows a simple cyclic permutation to guarantee adjacency, making verification straightforward.

For $n=3$ and $n=4$, an alternative would be an exhaustive computer enumeration of all permutations. While correct, this approach is unnecessarily cumbersome compared with the combinatorial impossibility arguments.