Two squares on an $8\times 8$ chessboard are called adjacent if they have a common edge or common corner. Is it possible for a king to begin in some square and visit all squares exactly once in such a way that all moves except the first are made into squares adjacent to an even number of squares already visited?
Problem
Source: Baltic Way 1999
Tags: combinatorics proposed, combinatorics
mahanmath
23.12.2010 19:53
No , Assume in this path the number of adjacent squares to the first square (in the path) after $(i,j)$ is $f(i,j)$ . Now compute the $S= \Sigma f(i,j)$ over all the pairs of $i,j$ . From the condition only one $f(i,j)$ is odd (i.e the square which we start our tour) so $S$ is odd . But ...
MathPanda1
03.04.2015 04:14
Is it true that the king must go in the path of a staircase with side-length 1?
Takeya.O
28.10.2015 08:14
The answer is NO. proof）Each square A, Let f（A）denotes the number of adjacent squares to the A already visited. We consider the following amount in each step. S＝Σ（A：already visited） f（A） For example, after first step S＝2,after second step S＝6. After each step（except for first step）, S is increased by 0 mod 4.（easily verified） So after final step, S≡2 mod 4. But we can calculate final S by definition, S＝3・4＋5・6・4＋8・36≡0 mod 4 This is contradiction！ The proof is completed.