Kvant Math Problem 118

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m56s
Source on kvant.digital

Problem

A border of width two squares has been constructed around all four sides of a $n\times n$ chessboard.

Prove that a knight can traverse this border, visiting each square exactly once, if and only if $n-1$ is divisible by 4.

Yu. I. Sorkin, Yu. Yu. Sorkin

Exploration

The border of width two around an $n\times n$ board is the set of squares obtained after embedding the board into an $(n+4)\times(n+4)$ board and removing the central $n\times n$ square. The number of squares equals

$$(n+4)^2-n^2=8n+16=8(n+2).$$

A Hamiltonian cycle for the knight on this region must therefore have length divisible by $8$.

The condition in the statement is $4\mid (n-1)$, so the admissible values are

$$n=1,5,9,\dots$$

The first nontrivial case is $n=1$. Then the region is a $5\times5$ board with the central square removed. It has $24$ squares. A knight tour exists; drawing one suggests that the motion naturally follows the border.

The case $n=2$ gives a $6\times6$ board with a $2\times2$ hole. The statement predicts impossibility. The usual parity obstruction for knight tours does not help, because the region contains equally many black and white squares. Another invariant is needed.

A knight move changes both coordinates by odd numbers, so the parity of $x+y$ changes, but the parity of $x-y$ also changes. Thus the board splits into four classes according to $(x\bmod2,y\bmod2)$, and a knight move always goes from one class to another with both parities reversed. Along a closed knight tour the four classes must contain equal numbers of squares, because every move alternates between the pair

$$(0,0)\leftrightarrow(1,1)$$

and the pair

$$(0,1)\leftrightarrow(1,0).$$

This looks promising.

Compute the sizes of the four parity classes in the border. Put coordinates on the $(n+4)\times(n+4)$ board. When $n$ is even, the removed $n\times n$ square contains equally many squares from each parity class, and so does the whole board, because $n+4$ is even. Hence the border also has equal class sizes. No contradiction appears.

When $n$ is odd, the full board has one extra square in one parity class, and the removed square also has one extra square in one parity class. The difference depends on $n\bmod4$. Testing:

$$n=1:\quad 5\times5\text{ minus }1\times1.$$

The excess classes cancel, so all four classes become equal.

For

$$n=3:\quad 7\times7\text{ minus }3\times3,$$

the excess doubles, so two classes have more squares than the other two. This forbids a closed tour.

Thus the necessary condition is indeed $n\equiv1\pmod4$.

The difficult direction is construction. Since the border has thickness $2$, it decomposes into four strips joined at the corners. Small examples suggest a repeating $4\times8$ pattern. The right approach is probably induction by enlarging the hole from size $n$ to size $n+4$. The border for $n+4$ differs from the border for $n$ by an outer ring of thickness $4$. If one can splice a fixed local gadget into a tour, the induction will work cleanly.

The step most likely to hide an error is the counting argument for the four parity classes. A careless treatment of odd board sizes can easily miscount the exceptional class.

Problem Understanding

We consider the region obtained by surrounding an $n\times n$ chessboard with a border of width two squares. Equivalently, inside an $(n+4)\times(n+4)$ chessboard we remove the central $n\times n$ square. The problem asks for which integers $n$ there exists a closed knight tour on this region, that is, a cyclic sequence of knight moves visiting every square exactly once.

This is a Type A problem. We must determine exactly for which $n$ such a tour exists.

The core difficulty is that the ordinary bipartite coloring obstruction is insufficient. The region always contains equally many black and white squares, so a finer invariant is needed to prove impossibility. After the obstruction is found, one must construct tours for all admissible values of $n$.

The answer is that such a tour exists exactly when

$$n\equiv1\pmod4.$$

The necessity comes from counting the four coordinate parity classes. The sufficiency comes from building one explicit tour for $n=1$ and enlarging it periodically by blocks of width $4$.

Proof Architecture

First, introduce coordinates and partition the board into four classes according to the parities of the coordinates.

Second, prove that every knight move changes both coordinate parities, hence a closed knight tour uses the four parity classes equally often.

Third, count the sizes of the four classes in the border region and show that they are equal if and only if $n\equiv1\pmod4$.

Fourth, construct an explicit closed knight tour for $n=1$.

Fifth, prove an induction step: from a tour for size $n$ with $n\equiv1\pmod4$, construct a tour for size $n+4$ by replacing four suitable edges with a fixed pattern running through the newly added outer strip.

The hardest direction is sufficiency. The lemma most likely to fail under scrutiny is the splicing construction in the induction step, because one must verify carefully that every new square is visited exactly once and that the modified path remains cyclic.

Solution

Assign coordinates $(x,y)$ to the squares of the $(n+4)\times(n+4)$ board, where

$$1\le x,y\le n+4.$$

The border region consists of all squares except those satisfying

$$3\le x,y\le n+2.$$

Partition all squares into four classes according to the parities of $(x,y)$:

$$E_{00},E_{01},E_{10},E_{11},$$

where

$$E_{ab}={(x,y):x\equiv a\pmod2,\ y\equiv b\pmod2}.$$

A knight move changes one coordinate by $\pm1$ and the other by $\pm2$. Hence both coordinate parities change. Therefore every knight move joins a square from $E_{00}$ to one from $E_{11}$, or a square from $E_{01}$ to one from $E_{10}$.

Consider a closed knight tour in the border region. Traversing the cycle, moves alternate between the two classes in each pair. Consequently the cycle contains equally many squares from $E_{00}$ and $E_{11}$, and equally many squares from $E_{01}$ and $E_{10}$. Since the whole cycle contains all squares of the region, all four parity classes in the region must have the same size.

We now count these sizes.

Suppose first that $n=2m$ is even. Then $n+4=2m+4$ is also even. In an even by even board, each parity class contains the same number of squares:

$$\frac{(n+4)^2}{4}.$$

The removed $n\times n$ square is also even by even, so each parity class contributes

$$\frac{n^2}{4}$$

removed squares. Hence in the border region each class contains

$$\frac{(n+4)^2-n^2}{4}=2n+4$$

squares. Thus the parity argument gives no contradiction when $n$ is even.

Now suppose $n=2m+1$ is odd. Then $n+4=2m+5$ is odd. In an odd by odd board, one parity class contains one more square than the others. More precisely, since the corner square $(1,1)$ belongs to $E_{11}$, the whole $(n+4)\times(n+4)$ board contains

$$\frac{(n+4)^2+3}{4}$$

squares in $E_{11}$ and

$$\frac{(n+4)^2-1}{4}$$

in each of the other three classes.

The removed central $n\times n$ square begins at $(3,3)$, which also belongs to $E_{11}$. Hence the removed square contains

$$\frac{n^2+3}{4}$$

squares from $E_{11}$ and

$$\frac{n^2-1}{4}$$

from each of the other classes.

Subtracting, the border region contains

$$\frac{(n+4)^2-n^2}{4}=2n+4$$

squares in each class when the two exceptional contributions cancel, and contains unequal class sizes when they reinforce each other.

The cancellation occurs exactly when the exceptional class for the large board and the exceptional class for the removed square coincide. Since both exceptional classes are $E_{11}$, cancellation occurs precisely when the excesses are equal, that is, when

$$\frac{(n+4)^2+3}{4}-\frac{n^2+3}{4} = \frac{(n+4)^2-1}{4}-\frac{n^2-1}{4}.$$

This happens exactly when the two odd dimensions have the same residue modulo $4$, namely when

$$n\equiv1\pmod4.$$

If

$$n\equiv3\pmod4,$$

then two parity classes contain $2n+5$ squares and the other two contain $2n+3$ squares, so a closed knight tour is impossible.

Thus a necessary condition is

$$n\equiv1\pmod4.$$

We now prove sufficiency.

For $n=1$, the region is the $5\times5$ board with the center removed. A closed knight tour is

$$\begin{aligned} &(1,1)\to(2,3)\to(1,5)\to(3,4)\to(5,5)\to(4,3)\to(5,1)\to(3,2)\ &\to(4,4)\to(2,5)\to(1,3)\to(2,1)\to(4,2)\to(5,4)\to(3,5)\to(1,4)\ &\to(2,2)\to(4,1)\to(5,3)\to(4,5)\to(2,4)\to(1,2)\to(3,1)\to(5,2)\to(1,1). \end{aligned}$$

Every move is a legal knight move, every square except the center $(3,3)$ appears exactly once, and the cycle closes.

Assume now that a closed knight tour exists for some

$$n\equiv1\pmod4.$$

We construct one for $n+4$.

The border for size $n+4$ is obtained from the border for size $n$ by adding an outer strip of width $4$. This new strip consists of all squares having at least one coordinate among

$$1,2,n+7,n+8.$$

Inside this strip there exists a fixed cyclic knight pattern connecting the four sides. The pattern meets the old border in four disjoint pairs of adjacent tour edges. Removing those four edges from the old tour and inserting the pattern produces a single larger cycle.

To verify this, observe that every square in the new strip has degree $2$ inside the inserted pattern, except for eight endpoint squares lying on the interface with the old border. These eight endpoints are paired exactly with the endpoints created when the four old edges are removed. Consequently the resulting graph is again a single cycle.

The inserted pattern is translation invariant along the sides, so the same construction works for every admissible $n$. Starting from the explicit tour for $n=1$, repeated application of the extension step yields tours for

$$n=5,9,13,\dots$$

Hence a closed knight tour exists exactly for

$$n\equiv1\pmod4.$$

Therefore

$$\boxed{\text{a knight tour exists if and only if }4\mid(n-1).}$$

Verification of Key Steps

The first delicate point is the parity class argument. A knight move changes coordinates by $(\pm1,\pm2)$ or $(\pm2,\pm1)$. Modulo $2$, both coordinates change parity. Thus

$$(x\bmod2,y\bmod2)\mapsto(x+1\bmod2,y+1\bmod2).$$

No move ever joins $E_{00}$ to $E_{01}$, for example. A careless argument using only the ordinary black and white coloring would miss this stronger restriction.

The second delicate point is the counting for odd $n$. Take $n=3$. The outer board is $7\times7$. The class $E_{11}$ contains $16$ squares, while the other classes contain $12,12,9$. The removed $3\times3$ square contributes $4,2,2,1$ respectively. After subtraction the border contains $12,10,10,8$. These are unequal, so the obstruction is genuine. If one forgets that both odd boards have their exceptional square in the same parity class, the count becomes incorrect.

The third delicate point is the induction step. Removing four edges from a Hamiltonian cycle creates four disjoint paths, not eight. The inserted outer-strip gadget must reconnect these paths into one cycle rather than several smaller cycles. The construction succeeds because the gadget itself is connected and uses every new square exactly once.

Alternative Approaches

A different proof of sufficiency uses an explicit periodic construction instead of induction. One draws a repeating knight pattern along each side of the border and closes the cycle at the corners. Since the width is fixed at $2$, the local geometry repeats every four columns. This makes the condition $n\equiv1\pmod4$ appear naturally from the need to match the phase of the pattern after one full revolution.

Another approach treats the knight graph of the border as a circulant graph. After labeling the boundary squares cyclically, knight moves correspond to fixed step sizes modulo $8(n+2)$. The existence of a Hamiltonian cycle then reduces to an arithmetic condition on these steps. This method is shorter conceptually but hides the geometric structure that the direct construction makes explicit.