3
$\begingroup$

A chess knight sits on a $3\times 4$ board. Is it possible for the knight to jump into the $12$ squares without jumping twice in any of them and ending and starting in the same box? What if it starts and ends in the different boxes?

I have drawn the graph that represents this problem and by looking at it I know that the answer to the first question is that it is impossible, but the second one is possible. However I can't find a mathematical reasoning to prove this. I know that my problem is equivalent to finding a hamiltonian cycle in the first case and a hamiltonian path in the second, but I don't know how to do this in any other way that trying to draw different paths. Could someone please help me with the mathematical reasoning?

$\endgroup$
0

2 Answers 2

3
$\begingroup$

Let's number the squares on the board in the conventional way:

a4 b4 c4
a3 b3 c3
a2 b2 c2
a1 b1 c1

If we look at squares a1, b4, and c1, there are only two possible moves from each of them. If these squares are in the middle of a tour - and that's always the case for a closed tour - then both of those moves have to be part of the tour: one entering the square and one leaving.

However, putting those two moves together gives a cycle of length $6$: a1 - b3 - c1 - a2 - b4 - c2 - a1. Instead of a tour that visits all $12$ squares, we end up with two subtours: this cycle, and its mirror image a4 - b2 - c4 - a3 - b1 - c3 - a4. So a closed tour is impossible.

For an open tour, we can just pick a move, such as a3 - c2, that goes between the two cycles of length $6$, and use it to stitch them together into a path. Just finding a path that works should be enough for a complete solution to this part.

$\endgroup$
1
$\begingroup$

It is well-known that a closed knight's tour on $3\times 4$-board is impossible. I'll try to recall the proof.

An open tour exists, see, for instance, the picture below.

enter image description here

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .