25
$\begingroup$

On a 15x15 chessboard there are 15 rooks that do not attack each other (via ordinary rook moves). Then each of the rooks makes one move like that of a knight.

Is it possible that after all this is done, the 15 rooks still do not attack each other (via ordinary rook moves)?

$\endgroup$
6
  • $\begingroup$ essentially, create a path of fifteen moves for a knight ending on the starting square on a 15x15 chessboard such that no position is in the same column or row as a different position $\endgroup$
    – Slepz
    Feb 23, 2016 at 20:15
  • $\begingroup$ Possibly relevant: I think this is possible for any $N\times N$ board with $N$ a multiple of 4. $\endgroup$
    – dpwilson
    Feb 23, 2016 at 20:44
  • $\begingroup$ @dpwilson There's an easy way to do that - four knights on a diagonal in a 4x4 can move to the other diagonal. Have all the knights of the $N\times N$ board be on a diagonal. Treat each group of four knights as if they were on a 4x4. $\endgroup$
    – Rob Watts
    Feb 23, 2016 at 20:54
  • $\begingroup$ @RobWatts: Yes, that is why I proposed that it is possible. $\endgroup$
    – dpwilson
    Feb 23, 2016 at 21:06
  • $\begingroup$ @dpwilson: $6 \times 6$ is also possible. Start with a diagonal, then move $a1 \to b3$, $b2 \to d1$, $c3 \to a2$, and similarly with the next three ($d4 \to f5$, $e5 \to c6$, $f6 \to e4$). This means any even number is achievable (except $2 \times 2$ of course). $\endgroup$ Feb 23, 2016 at 23:36

2 Answers 2

39
$\begingroup$

No

Since there is (initially and finally) a rook in each row and column, we can say the sum of all rooks' X and Y positions must be equal to 2 $\times$ (15 + 14 + ... + 1) = 120.

A knight's move will increment the rook's (X + Y) by +3, +1, -1, or -3, all of which are odd numbers.

The sum of 15 odd numbers (15 knight moves) is an odd number.

Since we are performing 15 moves, we are adding an odd number to the sum of the rooks' X and Y positions.

The final sum of the rooks' X and Y positions cannot be equal to the initial sum since performing 15 knight moves adds a non-zero number to that sum.

Since the initial sum is 120, the final sum cannot be 120 and therefore can't be a legal (non-attacking) position.

This proof can be extended to any $N\times N$ board where $N$ is odd.

$\endgroup$
1
  • 2
    $\begingroup$ An alternative but similar approach would be to say that if there are an odd number of knight moves, either an odd number must have a single-space vertical move, or an odd number must have a single-space horizontal move. If the number of short vertical moves is odd, the number of rooks moving from even to odd rows won't match the number moving from odd to even. Likewise for horizontal moves and even/odd columns. $\endgroup$
    – supercat
    Feb 24, 2016 at 16:26
0
$\begingroup$

Yes, in at least three cases that I can think of:

  1. The board wraps itself - i.e. from the top row, move 1 up, and you are now on the bottom row. In that case, all of the rooks make an identical move, and they are still safe.

  2. You said all the rooks make one move. You didn't say, that they make ONLY one move. So, the rooks simple move out, then back to their original position.

  3. The rooks move like knights. Presumably they also take like knights. In that case, I think the solution is obvious ;).

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.