Question

Imagine a prison consisting of 64 cells arranged like the squares of an 8-by-8 chessboard. There are doors between all adjoining cells. A prisoner in one of the corner cells is told that he will be released, provided he can get into the diagonally opposite corner cell after passing through every other cell exactly once. Can the prisoner obtain his freedom?


Here is a solution titled Exercise 3 Page 3 but I do not quite follow. I understand why it wouldn't work, just not this argument or how to really defend other than talking one through without showing the math.

http://jade-cheng.com/uh/coursework/math-475/homework-01.pdf

Answer 1

The correct answer is NO, he cannot obtain his freedom

Reason: The reason for not obtaining the freedom is the symmetry of the chessboard game which is of the size 8X8

Let us suppose the prisoner start from white block, then the path will be consisting of alternate black and white blocks.

Due to the symmetry of chess, in what ever matter he try he will reach the opposite color block, since each moves corresponds to the change in color, since the maximum number of steps will be 63, hence he will land up in the different color from which he has started, due to which he never will be able to obtain his freedom.

If this symmetry was not present or the box contains 9X9 maze, then maximum steps will be 80 and in that case, he will land in opposite color and will be free

So for any 2nX2n floor maze, he won't be able to escape from the prison and will be able to escape from (2n+1) X (2n+1)