Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider square grid of even sides ($2n \times 2n$). It is easy to see that there must exist Hamiltonian cycle on the corresponding grid graph. Such a cycle is called balance if the number of vertical edges equal the number of horizontal edges. It is easy to construct balance Hamiltonian cycles for odd $n$. But for even $n$ I could not contruct such balance cycles nor can I prove that those cycles don't exist. Question : Does there exist balance Hamiltonian cycle on the grid for even $n$?

Curiously I could not find a lot of research material on this, despite it being quite a natural object. This is sometimes called meander http://oeis.org/wiki/Meanders_filling_out_an_n-by-k_grid_%28not_reduced_for_symmetry%29

There is also an article that characterize and enumerate (by an algorithm) these cycles. http://www.mat.univie.ac.at/~slc/s/s34erlangen.pdf

The cycle divides the squares grid into regions (and closes one of them), and all the regions are tree (no cycle of squares that share edge). I feel that the answer to the original question will come from a clever insight into those trees.

Edit : I've made changes to make it more appropriate for MO.

share|improve this question
    
the reason for the question being...? –  Anthony Quas Mar 24 '13 at 20:42
1  
It is a well-known olympiad problem. –  Ilya Bogdanov Mar 24 '13 at 20:49
1  
A "hobbled Rook" is otherwise known as a Wazir, "a very old piece, appearing in some very early chess variants, such as Tamerlane chess." en.wikipedia.org/wiki/Wazir_(chess) –  Noam D. Elkies Mar 24 '13 at 21:10
    
Do you mean, "visit each square exactly once in an 8 by 8 chessboard?" If not, it seems very easy to do. –  Noah S Mar 24 '13 at 21:20
    
@Noah. yes, it's essentially a Hamiltonian cycle on the square grid –  John Mar 24 '13 at 21:26

1 Answer 1

Only a longer comment, not a complete answer.

I think of a $2n \times 2n$ chess board, where paths connect midpoints of squares. Let the total area of the board be $2n \times 2n$. Then the closed region (the tree), encloses an area of independent of the cycle, namely $2n^2-1$.

I have not proved this, but it seems straightforward to prove that trees with certain properties, and Hamiltonian cycles are in bijection.

When $n$ is odd, we can make a rotationally-symmetric tree, (where each of the four arm is a spiral, for example) and thus constructing a balanced path, since there is center vertex for the tree, so the $2n^2-2$ (which is divisible by $4$), can be distributed evenly in the four quadrants.

If $n$ is even, we still can put one vertex of the tree in the middle, but the $2n^2-2$ is now not divisible by $4$, and I believe this can be exploited to somehow show that said circuit is impossible.

share|improve this answer

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.