Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)?

share|improve this question
    
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 – Slepz Feb 23 at 20:15
    
Possibly relevant: I think this is possible for any $N\times N$ board with $N$ a multiple of 4. – dpwilson Feb 23 at 20:44
    
@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. – Rob Watts Feb 23 at 20:54
    
@RobWatts: Yes, that is why I proposed that it is possible. – dpwilson Feb 23 at 21:06
    
@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). – Tyler Seacrest Feb 23 at 23:36
up vote 39 down vote accepted

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.

share|improve this answer
2  
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. – supercat Feb 24 at 16:26

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 ;).

share|improve this answer
1  
This isn't a lateral-thinking question. – Scimonster Feb 24 at 14:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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