0
$\begingroup$

Prove that on a chessboard that has dimension $4 \times m$ there doesn't exist a knights tour in which we return to square we started at.

I know that we need to turn each square into a vertice and then add edges between vertices where a valid move exists. Now we must show that this graph is not Hamiltonian, which I am unsure how to do. Any help is appreciated, thanks!

$\endgroup$
1
$\begingroup$

HINT

Show that since you can't move between rows 1 and 4, in a (supposed!) Tour you can't move between rows 2 and 3 either.

So, what are all the colors of the squares visited in rows 2 and 3 like in such a Tour?

$\endgroup$
  • $\begingroup$ The only thing I am seeing is that they all have degree 3, other than that I am unsure how to proceed. $\endgroup$ – Justin Stevenson Mar 20 '17 at 22:45
  • $\begingroup$ Ah, right, I was confused with an Eulerian cycle :( $\endgroup$ – Bram28 Mar 20 '17 at 22:47
  • $\begingroup$ @JustinStevenson Ok, new HINT! $\endgroup$ – Bram28 Mar 20 '17 at 23:20
  • $\begingroup$ Why can't you move between row 2 and 3? $\endgroup$ – Justin Stevenson Mar 20 '17 at 23:57
  • $\begingroup$ Not if you want a Hamiltonian tour ... how many squares are there in rows 1 and 4? How many are there in rows 2 and 3? $\endgroup$ – Bram28 Mar 21 '17 at 0:24
0
$\begingroup$

You can solve this through colouring the squares like so

1 B 1 B 1 B 1 B ...
2 A 2 A 2 A 2 A ...
A 2 A 2 A 2 A 2 ...
B 1 B 1 B 1 B 1 ...

You start from the top left corner with colour $1$. Every field $1$ is preceeded and followed by a $2$. Because every field has to be in the tour, all $1$'s and $2$'s are in the sequence of moves, whereby the number of $1$'s and $2$'s are the same.

But the $A$'s must also lie in the sequence. In order to do that, there are only these two cases:

  • Case 1: To get to an $A$, you are coming from a $2$. In this case, to get to a $1$, you have to go to a $2$ first in oder to do that, i.e. you have more $2$'s then $1$'s. Contradiction. An example would be like $$\ldots \rightarrow \underline{1 \rightarrow 2} \rightarrow A \rightarrow \boxed2 \rightarrow \underline{1 \rightarrow 2} \rightarrow \ldots$$ or like $$\ldots \rightarrow \underline{1 \rightarrow 2} \rightarrow \underline{A \rightarrow B} \rightarrow A \rightarrow \boxed2 \rightarrow \underline{1 \rightarrow 2} \rightarrow \ldots$$ Note that the boxed $2$ isn't in a pair with a $1$.

  • Case 2: To get to an $A$, you are coming from a $B$. Like the $1$'s, every $B$ is preceeded and followed by an $A$. Therefore, to get to this $B$, you have to come from an $A$, so there is no first $A$ you moved to. Contradiction.

Therefore there is no colosed tour on the board.

Additional note: This solution is from the excellent and highly recommended book Problem-Solving Strategies by Arthur Engel. Some olympiad problems you will face come from this book. There's also a lot of must-no-theory in there. Give it a try: PDF link.

$\endgroup$

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.