Prove that no closed knight's tour is possible on the $2 \times 2 \times 2 \times 2 \times 2 \times 2$ chessboard

103 Views Asked by At

Let $n,k \in \mathbb{N}-\{0,1\}$. The generalization of the closed knight's tour problem to higher dimensions asks to move a knight along the $n^k$ cells of a $n \times n \times \cdots \times n$ checkboard belonging to the Euclidean space $\mathbb{R}^k$, touching the centres of all of them only once, and then returning to the starting square at move $n^k$.

Now, as suggested by the definition provided by the FIDE LAWS of CHESS (see Article 3.6), assume that the knight is a piece whose move rule states that it can move to any square/cell of the chessboard that is $\sqrt{5}$ (chessboard) units away from the square where it stands.

Then, assume $n=2$. I have proven here that such a closed knight's tour is always possible as long as $k>6$, while it cannot clearly exists any (possibly open) knight's tour for any $k<6$ (i.e., a knight can perform its special move only once on the $2 \times 2 \times 2 \times 2 \times 2$ board, from a random vertex of the hypercube to the opposite vertex and then there are no other — unvisited — vertices at a distance greater than or equal to $\sqrt{5}$ from the current one).

My question is to find an easy proof that no closed knight's tour exist on the $2 \times 2 \times 2 \times 2 \times 2 \times 2$ board.

1

There are 1 best solutions below

10
On BEST ANSWER

Unless I'm mistaken, there is indeed such a path (many such paths!) on the six-dimensional board: each move must change five different coordinates, so it can be thought of as a change of a single coordinate followed by an inversion of all the coordinates.

Now, consider a six-bit Gray code, in particular starting at 000000: such a code will have only one bit changing at a time. This means that the even-index positions will have an even number of bits set and the odd-index positions will have an odd number of bits set. Now, since the inverse of a word with an odd number of set bits is also a word with an odd number of set bits, inverting all of those words must introduce a permutation on them (since inversion is 'reversible') and so will also cover all the odd words. This should mean that if we take any Gray code and reverse all of the odd words, we get a valid Knight's Tour on the $2\times2\times2\times2\times2\times2$ board. And there are a lot of Gray codes, even taking the permutation symmetry into account: https://oeis.org/A066037