2
$\begingroup$

I am taking a course on graph theory right now and we were posed the following question:

Show that if $n$ is odd, a knight on an $n \times n$ chessboard can not make a closed tour of the chessboard (making only jumps that are allowed by chess rules) in such a way that every square of the board is traversed exactly once.

My answer would move into this direction:

any odd number squared also produces an odd square $n^2=(2k+1)^2= 4k^2 +2k +1= 2(2k^2+2k)+1$ which is the amount of squares on the board. The sum of the white and black squares is odd, therefore the amount of black squares is unequal to the amount of white squares. When a knight makes a jump, he jumps to a square with a different color. Suppose there are $l$ black squares on this chess board and $l+1$ white squares, such that $l+(l+1)=2l+1=n^2$ is the total number of squares again.

My classmates came up with the following argument:

Suppose we start on a black square, we make $2l-1$ jumps, this is an odd number so we end up at a white square, we have already exhausted all of the black squares $1+ 2l-1=2l$ (so just one white left)so now we cannot jump to the last white square because we are missing an intermediate black square.

Now suppose we start on a white square, there are $l$ white squares and $l$ black ones left. We then make $2l$ jumps, divided into $l$ white squares and $l$ black squares, everything is fine and we don't reach a contradiction, what is going on here? what is my reasoning error? My classmates suggested that we would be missing a square to make the final jump, but I don't see it.


Edit:

The contradiction in the white case arises that after we make $2l$ jumps, we have reached all the white squares that we did not start out with, but we have also exhausted all the black squares, we cannot possibly go back, because we would need an additional black square to get back - we don't have that square.

$\endgroup$
  • 1
    $\begingroup$ Just counting the number of black vs white squares is not going to be enough: yes, there will be one more white than black (or vice versa), but all that that means is that you need to start on a square of that color in order to do a tour ( of course, a closed tour would be impossible) ... but there is no contradiction in that ... yet. $\endgroup$ – Bram28 Nov 25 '18 at 20:31
  • $\begingroup$ It depends what you mean by a "knight's tour". If it has to end at the same place it started a simple party argument shows that it can't be done. And no such is possible for a $3\times 3$ square because there is no jump to or from the middle. $\endgroup$ – Mark Bennet Nov 25 '18 at 20:34
  • $\begingroup$ What do you mean by "party" argument? $\endgroup$ – Wesley Strik Nov 25 '18 at 20:46
  • 1
    $\begingroup$ "party" is a typo for "parity". $\endgroup$ – Hew Wolff Nov 25 '18 at 21:02
4
$\begingroup$

There is no reasoning error in your argument. On some odd-by-odd chessboards, it is possible to have a knight's tour, as the following $5 \times 5$ example shows:

5x5 knight's tour

The argument by considering black squares and white squares does show that there is no closed knight's tour that visits every square then returns to the start. After all, if there are $l$ black squares and $l+1$ white squares, then any knight's tour must begin and end on a white square - and so there can be no knight's move from the last square of the tour to the first.

If the knight's tour is not required to be closed, then that is a mistake in the problem: the diagram above is a counterexample.

And the $5\times 5$ board is not an isolated exception. As Hew Wolff points out in the comments, Wikipedia cites some results showing that a knight's tour exists on any $n \times n$ chessboard where $n\ge 5$ (and in fact on any $n \times m$ chessboard where $n\ge 5$ and $m\ge 5$).

$\endgroup$
  • 2
    $\begingroup$ And in fact according to Wikipedia, "on any rectangular board whose smaller dimension is at least 5, there is a (possibly open) knight's tour." $\endgroup$ – Hew Wolff Nov 25 '18 at 20:31
  • 1
    $\begingroup$ @HewWolff Thank you for pointing that out! Assuming you have no objections, I have added your comment to the end of my answer. $\endgroup$ – Misha Lavrov Nov 25 '18 at 20:35
  • $\begingroup$ What I think that the approach should be is to show that such a path is NOT Hamiltonian. $\endgroup$ – Wesley Strik Nov 25 '18 at 20:42
  • 1
    $\begingroup$ @WesleyGroupshaveFeelingsToo But the path is Hamiltonian, which you can tell by following the path in the diagram. What I am saying is that unless the knight's tour is required to be a closed one, then the problem is ill-posed, because the knight's tour does exist. $\endgroup$ – Misha Lavrov Nov 25 '18 at 20:47
  • 3
    $\begingroup$ @WesleyGroupshaveFeelingsToo It's possible that the textbook you're using defines a tour (of a graph) as a closed path by default. Confusion arises because in the case of the knight's tour problem, it is traditional to use the word "tour" for both and specify "closed" separately. Either way, we now know the answer for both cases (closed and open) and so there is no issue of mathematics left, only an issue of terminology. $\endgroup$ – Misha Lavrov Nov 25 '18 at 20:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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