Closed tour of a Knight

For discussing Olympiad Level Combinatorics problems
tanmoy
Posts:312
Joined:Fri Oct 18, 2013 11:56 pm
Location:Rangpur,Bangladesh
Closed tour of a Knight

Unread post by tanmoy » Sat Oct 15, 2016 7:36 pm

When a Knight moves in chess, it can move to a square that is away two squares horizontally and one square vertically,or two squares vertically and one square horizontally.A closed tour for a Knight is a sequence of moves,which have the Knight start and end in the same square and visit each other square exactly once.On a $4 \times 3$ board,is there a possible closed tour for a Knight?
"Questions we can't answer are far better than answers we can't question"

samiul_samin
Posts:1007
Joined:Sat Dec 09, 2017 1:32 pm

Re: Closed tour of a Knight

Unread post by samiul_samin » Thu Mar 01, 2018 6:47 pm

Hint
Use proof by contradiction & invariance pinciple
Answer
NO.
$4×3$ Chess Board
Screenshot_2018-03-01-18-22-01-1.png
Answer
According to the given chessboard the close knight tour is possible if and only if the knight can move from $A$ to $T$ and touch every squares exactly Once.

Let,this tour is possible.So,the knight has to move to $I$ before $T$.There is only $2$ ways to move to $I$, they are $R\rightarrow I$ and $O\rightarrow I$ It is obvious that $O\rightarrow I$ is not possible.So,the moves should be,$R\rightarrow I$,$I\rightarrow O$,$O\rightarrow I$.
Now if the knight wants to move from $A$ to $R$ under the condition of question in $8$ move,it can't do so.Because,In every move it alters the color of the square.If $A$ is black,$R$ is also black.But,move number is even.
A contradiction.
So,we are done.It is not possible.

samiul_samin
Posts:1007
Joined:Sat Dec 09, 2017 1:32 pm

Re: Closed tour of a Knight

Unread post by samiul_samin » Sat Mar 09, 2019 7:59 pm

Ignore the above solution.
Correct Solution

Let the tour is possible.
Total move $=12-1=11$
In every move it alters the color of the square.If the starting square is black,the ending square is not black.(Imagine it as a traditional chess board)
But,move number is odd.
A contradiction.
So,we are done.It is not possible.

Post Reply