17

Professor Erasmus has found a special way of moving a rook across a standard $8\times8$ chessboard that he modestly calls the "Professor-Erasmus-rook-tour". The professor claims that in this tour, the rook makes $64$ moves that visit all the $64$ squares of the chessboard. Every move is from some square to a horizontally or vertically adjacent square, and the very last move brings the rook finally back to its starting square. Exactly $32$ of these moves are in horizontal direction, and $32$ are in vertical direction.

Has the professor once again made one of his mathematical blunders, or do such rook tours indeed exist?

Gamow
  • 45,573
  • 10
  • 147
  • 381
  • 2
    Since he claims to have found one (as opposed to presenting a non-constructive proof that one exists), I would ask him to demonstrate this tour. If he does so successfully, then such tours exist. If he fails, then he has made another blunder. (But other valud tours may still exist). – KSmarts Feb 03 '15 at 18:09
  • 1
    When you say "to a horizontally or vertically adjacent square", do you indeed mean that the rook can move only one square orthogonally, rather that any number of spaces orthogonally as is usual for a chess rook? – xnor Feb 03 '15 at 18:23

2 Answers2

11

Update:

This problem can be simplified in the following way:

For an $n x n$ board where $n$ is even, make $\frac{n}{4}$ squares that are $2 x 2$.

This has $\frac{n^2}{2}$ horizontal and $\frac{n^2}{2}$ vertical moves.

Now, join any 2 adjacent shapes. When doing this, you will alter both the horizontal and vertical moves by 2.

Continue joining shapes until you have made 1 single shape taking up the entire board.

You can choose your adjustments so that for each join, you alternate between increasing and decreasing the horizontal moves.

To end up with a shape that has the same number of horizontal and vertical moves, it requires an even number of join operations, which requires an odd number of shapes.

Therefore, $\frac{n^2}{4}$ must be odd.

If $n = 8$ then $\frac{n^2}{4} = 16$. Because it is even, the number of join operations is odd, which means that you cannot end up with an identical number of horizontal and vertical moves.

So Professor Erasmus is incorrect. This cannot be done with an $8 x 8$ chessboard.

Original:

Professor Erasmus has made a mistake. He should have chosen a board with a side that is divisible by 2 but not 4.

2x2 board: Trivial to see that 4 moves must be 2 horizontal and 2 vertical.

4x4 board: Few enough paths to see that the best you can get is a difference of 4 between horizontal and vertical. Also, the worst you can get is a difference of 4.

6x6 board: Follow the outside edge for 17 moves, then zig-zag back through the center. Total of 18 horizontal, 18 vertical. This is one of many ways to achieve this.

8x8 board: Again, the best that you can do is a difference of 4 between horizontal and vertical.

I have not tried larger boards. I expect that my answer is accurate for them.

Joel Rondeau
  • 7,540
  • 1
  • 30
  • 44
  • What is the proof for the 8x8 board? – Trenin Feb 03 '15 at 17:51
  • I do not have a full proof for the 8x8 board. Given what I tried with the 4x4 and then 6x6 board and the fact that similar answers didn't get me any closer than 4 for the 8x8, I believe it to be correct. I'll see if I can put something together later. – Joel Rondeau Feb 03 '15 at 17:55
  • I'm in the same place as you. But, "I can't find one" doesn't mean, "there isn't one". I'm pretty sure there isn't, but I'm trying to prove it. – KSmarts Feb 03 '15 at 18:06
  • 2
    Re your proof: not every possible rook tour can be made by joining 2x2 squares together, right? – Lopsy Feb 03 '15 at 19:13
  • @Lopsy, I'm reasonably certain that every rook tour can be made this way for any $m x n$ board where $m$ and $n$ are both even. – Joel Rondeau Feb 03 '15 at 19:22
  • I'm not sure what you mean here, by "when [joining 2 shapes], you will alter both the horizontal and vertical moves by 2." – KSmarts Feb 03 '15 at 19:41
  • @KSmarts Take 2 squares at A1:B2 and C1:D2. To join them together, you remove the vertical lines (moves) at B1:B2 and C1:C2 and replace them with horizontal lines (moves) at B1:C1 and B2:C2. The joining can always be the replacement of 2 vertical lines with 2 horizontal lines of a $2 x 2$ square (or 2 horizontal with 2 vertical lines). – Joel Rondeau Feb 03 '15 at 19:50
  • Okay, I get it. I was thinking along these same lines, but you beat me to it. Also, I wasn't sure if it covered all tours. – KSmarts Feb 03 '15 at 20:03
  • @KSmarts I started with larger shapes that I'd have to join together. When I was trying to simplify that, I discovered that every one could be created from $2x2$ squares. Made the problem much simpler. – Joel Rondeau Feb 03 '15 at 20:11
1

Many tries, I always end up in 30 : 34. Is the start square important?

30

Pierre Begon
  • 404
  • 2
  • 8