>It seems that the total length of the
>horizontal segments is divisible by 4 if and only if m is
>not divisible by 4 and n is odd, but I can't prove this yet.
>Can someone prove this?

I think this works:

We may consider the tour as consisting of a sequence of horizontal and vertical segments, each of length 1, connecting centres of adjacent squares. This sequence forms a single closed loop. As each unit square with vertices at the centres of grid squares is either completely inside or completely outside the loop, we may divide the inside into such squares. Consider the graph on these inner squares as vertices, with edges joining only adjacent squares. This graph is connected but has no loops; it is a tree. So it has k-1 edges; there are k-1 pairs of adjacent squares. So if there are k inner squares then the perimeter (and so the number of edges in the loop) is the total perimeter of all of those squares, 4k, minus double the number of pairs of adjacent squares, 2(k-1). That is, it is 2k + 2. But as the tour passes through each square exactly once, this perimeter must equal mn. So k = (mn-2)/2.

Now number the files of the original chessboard from 1 up to n. Every offset square is bounded by exactly 1 vertical segment lying in an even numbered file. Further, if that segment is not in the loop then it lies on the boundaries of exactly 0 or 2 such inner squares. So k is congruent modulo 2 to the number of vertical edges of the loop which lie in even numbered files (call this latter number s).

Now in a given file, we consider the connected components consisting of vertical segments in the loop. In order to have a space of length 1 between any pair of these, introduce if necessary some components considered to have length 0 into the larger gaps. Suppose now that there are p vertical segments in the file. Then there are m - 1 - p gaps and so m - p connected components. So there are 2(m-p) horizontal edges in the loop with 1 end in that file (each connected component is adjacent to 2 such edges).

As all horizontal segments are counted in this way and there are [n/2] odd numbered columns (where [.] denotes the integer part) we have, letting h be the number of horizontal segments in the loop:

h = 2(m[n/2] - s)
= 2(m[n/2]) - 2k modulo 4
= 2(m[n/2]) - mn + 2.
= 2 if n is even, 2 - m if n is odd.

So h is congruent to 0 modulo 4 iff n is odd and 2-m is 0 modulo 4 iff n is odd and m isn't divisible by 4, as required.

Thankyou

sfwc
<><
Thankyou

sfwc
<><