|
|
|
|
|
|
|
|
CTK Exchange
Zvi
guest
|
Jun-26-06, 01:51 PM (EST) |
|
"Closed rook tour on a chessboard"
|
A rook makes a closed tour on a chessboard of m ranks and n files, visiting each square exactly once and returning to the starting point. The tour consists of horizontal segments and vertical segments. 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? (The length of a segment is measured between centers of squares, for example if the rook moves from d8 to f8 that's a horizontal segment of length 2.) |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
koko
guest
|
Jul-05-06, 08:02 PM (EST) |
|
2. "RE: Closed rook tour on a chessboard"
In response to message #0
|
Choose m=2 and n=3, then the coordinates of the squares are a1, b1, a2, b2, a3, c3. Move the rook from a1 to b1 to b2 to b3 to a3 to a2 to a1. Then the total length of the horizontal segments (a1 to b1 and b3 to a3) is 2, which is is not divisible by 4. |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
sfwc
Member since Jun-19-03
|
Jul-07-06, 07:39 AM (EST) |
|
4. "RE: Closed rook tour on a chessboard"
In response to message #2
|
>Choose m=2 and n=3, then the coordinates of the squares are >a1, b1, a2, b2, a3, c3. Move the rook from a1 to b1 to b2 to >b3 to a3 to a2 to a1. Then the total length of the >horizontal segments (a1 to b1 and b3 to a3) is 2, which is >is not divisible by 4. You seem to have ranks and files confused. Ranks are rows, files are columns. So in this case there are 2 rows, 3 columns. The segments a1b1 and b3a3 are therefore vertical. There are 4 horizontal segments, which fits the given result.Thankyou sfwc <>< |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
sfwc
Member since Jun-19-03
|
Jul-05-06, 08:02 PM (EST) |
|
3. "RE: Closed rook tour on a chessboard"
In response to message #0
|
>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 <>< |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
You may be curious to have a look at the old CTK Exchange archive. Please do not post there.
Copyright © 1996-2018 Alexander Bogomolny
|
|