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
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.