Crippled Rook
A crippled rook can move on a chessboard in the following way: from a square, it can move to an adjacent square sharing a common side, and every two consecutive moves must be at right angles (i.e., the rook makes a turn at every move).
A cycle is a sequence of squares which start and end at the same square, and traces out a valid path that the crippled rook can move according to the rules above. A non-intersecting cycle consists of pairwise distinct squares, with the sole exception of the starting and ending square.
What is the length of the longest possible cyclic, non-intersecting route of a crippled rook on a chessboard?
This problem is shared by Aman R. . It was created by Michal Rolinek.
Details and assumptions
The length of the route is the number of squares that the rook travels on.
The answer is 192.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
I don't know if there's an easy way to do this but here's how I did it (leaving some details to be worked out by the reader):
First, paint the board with four colors, such that no square is the same color as any of its 8 neighbors (and hence any four consecutive squares in a cyclic are four different colors). One color, let's say red, will be on only 1 4 2 / 4 = 4 9 squares.
I'll leave it for the reader to construct a cyclic of length 192 (i.e. which covers 48 of the 49 red squares). It remains to be shown that there is no cyclic which covers all 49 red squares.
Suppose the red squares in a cyclic (occurring every fourth move) are labeled in order, R 1 , R 2 , R 3 , etc. Then each R n + 1 is either 2 or 4 spaces away from R n ; and since 49 is odd, there would need to be and even number of the former, and hence an odd (and, in particular, nonzero) number of the latter.
So now suppose (WLOG) that after R 1 the cyclic moves “up, left, up, left” to get to R 2 ... this places heavy restrictions on access to the red square that is two spaces above R 1 , which I'll call R k . In particular, the cyclic would have to reach R k by a "left" move and leave it by an "up" move. But considering this topologically (I recommend drawing a picture here) this would mean that at some point, either while going from R 2 to R k or going from R k back to R 1 , the cyclic would have to pass in between two of those three squares. (Note that's equivalent to saying: If a cyclical path includes two parallel sides of square, in the same direction, then it must either cross itself or go inside the square.) But that would mean overlap. This completes the proof that there is no cyclic which covers all 49 red squares.