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.