Knights on Multidimensional Torus Chessboard How many knights can be placed on an $n \times n \times n \times\dots\times n$ torus board with $n$ odd so that if two knights are in non-attacking position (the knight moves by two squares in one dimension, one square in another), then the distance between them is greater than one king's move (assuming the king takes the shortest path between squares - for instance to move right one step, it does not move diagonal up right and come down)?
 A: For $n \geq 4$, pairs of knights are forbidden if and only if they are one "king's move" apart (they don't attack each other if they are adjacent, and if they are attacking they are not adjacent).  So, this problem is essentially asking how many non-attacking kings can be placed on an $$\overbrace{n \times n \times \cdots \times n}^m$$ toroidal board.
Construction: If we index the cells by $(\mathbb{Z}_n)^m$, we can place kings in the cells that have all coordinates in $\{0,2,4,\ldots,2\lfloor n/2-1 \rfloor\}$.  The number of non-attacking kings in this construction is thus $\lfloor n/2 \rfloor^m$.
This is the best possible for $n$ even, since any $\overbrace{2 \times 2 \times \cdots \times 2}^m$ subarray can have at most one king, and we can partition the board into $\lfloor n/2 \rfloor^m$ such subarrays.
I suspect that this is also the best possible for $n$ odd, but I'm unsure how to prove it.
(For non-toroidal boards, $\lceil n/2 \rceil^m$ is the best possible.  The argument above works for both even and odd $n$, in this case.)

The problem is equivalent to finding the size of a maximal independent set in the graph $C_n \square C_n \square \cdots \square C_n$ where $C_n$ denotes an $n$-cycle and $\square$ denotes the Cartesian product.  Or equivalently, the size of a maximal clique in its complement.
