Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I can't solve this question. anyone knows how I must solve?

You have a 6x3 chess board. How many forms exist to put a Knight in a square and with valid moviments pass in all squares but only one time in each one?

And with in a LxC chess board?

share|improve this question
    
Are you familiar with chess and what a valid move by a knight is (i.e., with how a knight is moved)? For what it's worth, and/or for those not familiar with chess, see knight (chess) –  amWhy Nov 2 '12 at 21:48
1  
You could start here and look at the Schwenk and Cull references. –  Brian M. Scott Nov 2 '12 at 21:50
1  
I won some chess tournaments, so yes, I know how a knight move. –  John Smith Nov 2 '12 at 21:52
    
This is actually a graph theory problem. Consider the graph whose vertices are the board squares and two vertices are linked by an unoriented edge if and only if the corresponding squares are linked by a single Knight move. Then the problem translates into that of finding the Hamiltonian circuits. –  Andrea Mori Nov 2 '12 at 22:02
1  
@John: See Wikipedia for LxC knight tours: It is possible if $(L, C) \in \{(5+, 5+), (3, 10+)\}$ provided $L \cdot C \in 2\mathbb{Z}$. –  TMM Nov 3 '12 at 23:40

2 Answers 2

up vote 3 down vote accepted

In the book "Across the Board" (Watkins, 2004) there's a nice explanation why no knight's tour (i.e. starting and ending at the same square) exists on the $6 \times 3$ chessboard:

Suppose there is a knight's tour. One can connect the squares formed by the tour to form a necklace. If you remove one piece of a necklace, the necklace breaks, but is still in one piece. Taking another piece from the necklace then breaks the necklace into at most two parts. But removing the two squares marked $\ast$ above disconnects the two square marked $\times$ from the rest of the board by knight moves. So we get three components, which is a contradiction. So no knight's tour exists on a $6 \times 3$ chessboard.

This could be extended to show that no knight's path exists. If we have a chain (i.e. an open necklace), and we remove $6$ pieces of the chain, we should be left with at most $7$ components. But if we remove the six squares marked below:

$$\begin{matrix} \cdot & \cdot & \times & \times & \cdot & \cdot \\ \cdot & \cdot & \times & \times & \cdot & \cdot \\ \cdot & \cdot & \times & \times & \cdot & \cdot \\ \end{matrix}$$

then we are left with $8$ components:

$$\begin{matrix} 1 & 2 & \times & \times & 5 & 6 \\ 3 & 4 & \times & \times & 7 & 8 \\ 2 & 1 & \times & \times & 6 & 5 \\ \end{matrix}$$

So there is no knight's path on a $6 \times 3$ chessboard either.

share|improve this answer
    
(The "quoted" part is not an actual, literal citation, but a description of the proof given in that book.) –  TMM Nov 2 '12 at 22:25

For a $6 \times 3$ board, it's impossible. Consider the board below, and the squares, marked with an $\times$.

$$\begin{matrix} \cdot & \cdot & * & \cdot & \cdot & \cdot \\ \times & \cdot & \cdot & \cdot & \times & \cdot \\ \cdot & \cdot & * & \cdot & \cdot & \cdot \\ \end{matrix}$$

The only way to get to these squares is through the squares marked with an $\ast$. But if you use both to get to one of them and to get out again, then you cannot reach the other marked square anymore. The only way to solve this is to start at one of these marked squares. By symmetry, we have two other such squares:

$$\begin{matrix} \cdot & \cdot & \cdot & \ast & \cdot & \cdot \\ \cdot & \times & \cdot & \cdot & \cdot & \times \\ \cdot & \cdot & \cdot & \ast & \cdot & \cdot \\ \end{matrix}$$

So we have to finish at another of these squares as well. So the first four and final four moves are determined, as, one of the following two scenarios:

$$\begin{matrix} \cdot & \cdot & 2 & 15 & \cdot & \cdot \\ 1 & 16 & \cdot & \cdot & 3 & 18 \\ \cdot & \cdot & 4 & 17 & \cdot & \cdot \\ \end{matrix} \qquad \text{or} \qquad \begin{matrix} \cdot & \cdot & 2 & 17 & \cdot & \cdot \\ 1 & 16 & \cdot & \cdot & 3 & 18 \\ \cdot & \cdot & 4 & 15 & \cdot & \cdot \\ \end{matrix}$$

In both cases, we need the remaining $10$ squares to connect the two ends of the chain to form a knight's path. This means that each of these $10$ points is connected to two other of these points (except for the ones next to $2$ and $17$). By starting with the corners, we get two chains of length $5$:

$$\begin{matrix} d & a & \cdot & \cdot & A & D \\ \cdot & \cdot & c & C & \cdot & \cdot \\ b & e & \cdot & \cdot & E & B \end{matrix}$$

There's just no way to connect $a/e$ to $A/E$, so there's no chain of length $10$ connecting these squares. So there is no knight's path on this board.

share|improve this answer
1  
It seems to me that we can reach all 8 of your marked squares without repeating any square twice. $\begin{matrix} \cdot & \cdot & 2 & 5 & \cdot & \cdot \\ 3 & 6 & \cdot & \cdot & 1 & 8 \\ \cdot & \cdot & 4 & 7 & \cdot & \cdot \\ \end{matrix}$. You're right that it's impossible on this board, but I don't see how your reasoning in this answer shows it. –  mixedmath Nov 2 '12 at 22:26
    
@mixedmath: Yes, you are right. The argument becomes a bit more lengthy now, so I definitely like my other answer better now... –  TMM Nov 3 '12 at 0:28

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.