C6 BGR (Bulgaria)
On a 999x 999 board a limp rook can move in the following way: From any square it can move
to any of its adjacent squares, i.e. a square having a common side with it, and every move
must be a turn, i.e. the directions of any two consecutive moves must be perpendicular. A non-
intersecting route of the limp rook consists of a sequence of pairwise di fferent squares that the
limp rook can visit in that order by an admissible sequence of moves. Such a non-intersecting
route is called cyclic, if the limp rook can, after reaching the last square of the route, move
directly to the fi rst square of the route and start over.
How many squares does the longest possible cyclic, non-intersecting route of a limp rook
visit?
Let us color the cells with four colors A, B, C and D in the following way
for (i,j) equivalent to (0,0) mod 2 use A
for (i,j) equivalent to (0,1) mod 2 use B
for (i,j) equivalent to (1,0) mod 2 use C
for (i,j) equivalent to (1,1) mod 2 use D
From an A-cell, the rook has to visit a B-cell or a C-cell. In the first case, the order of the colors of the cells visited is given by A, B, D, C, A, B, D, C ... and in the second case the order is given by A, D, B, A, C, D, B ... Since the route is closed it must contain the same number of cells of each color.
There are only 499^2 A-cells.It can be shown that the rook cannot visit all A cells on its route and hence the maximum possible number of cells in a route is 4( 499 ^2 -1). The four squares deducted from the total happen to be the four corners of the board.
Assume that the route passes through every single A cell. Color the A cells in black and white in a chessboard manner. A cells that are two cells apart are different colors. Since the number of A cells is odd, the rook cannot always alternate between black and white A cells. Let the two A cells of the same color which are four rook steps apart be (a,b) and (a+2, b+2) respectively.
There is only one path to take between these two squares. Let this path be (a,b), (a,b+1), (a+1,b+1), (a+1,b+2) and (a+2,b+2) we can say (a,b+1) is B otherwise we can interchange the rows and columns to be such that it is B.
Now let us look at the A cell vertically above which is (a,b+2) The only way the rook passes through it is via (a-1,b+2), (a,b+2) and(a,b+3) in this order. Hence to connect these two parts of the path, there must be a path connecting the cell (a,b+3) and (a,b) and also a path connecting (a+2,b+2) and (a-1,b+2)
But these are opposite vertices of a quadrilateral and paths are outside so they must interesect. But an intersection is only possible if a cell is visited twice and this is a contradiction.
Hence the number of cells must be at most 4. (499^2 -1)
On a 999x 999 board a limp rook can move in the following way: From any square it can move
to any of its adjacent squares, i.e. a square having a common side with it, and every move
must be a turn, i.e. the directions of any two consecutive moves must be perpendicular. A non-
intersecting route of the limp rook consists of a sequence of pairwise di fferent squares that the
limp rook can visit in that order by an admissible sequence of moves. Such a non-intersecting
route is called cyclic, if the limp rook can, after reaching the last square of the route, move
directly to the fi rst square of the route and start over.
How many squares does the longest possible cyclic, non-intersecting route of a limp rook
visit?
Let us color the cells with four colors A, B, C and D in the following way
for (i,j) equivalent to (0,0) mod 2 use A
for (i,j) equivalent to (0,1) mod 2 use B
for (i,j) equivalent to (1,0) mod 2 use C
for (i,j) equivalent to (1,1) mod 2 use D
From an A-cell, the rook has to visit a B-cell or a C-cell. In the first case, the order of the colors of the cells visited is given by A, B, D, C, A, B, D, C ... and in the second case the order is given by A, D, B, A, C, D, B ... Since the route is closed it must contain the same number of cells of each color.
There are only 499^2 A-cells.It can be shown that the rook cannot visit all A cells on its route and hence the maximum possible number of cells in a route is 4( 499 ^2 -1). The four squares deducted from the total happen to be the four corners of the board.
Assume that the route passes through every single A cell. Color the A cells in black and white in a chessboard manner. A cells that are two cells apart are different colors. Since the number of A cells is odd, the rook cannot always alternate between black and white A cells. Let the two A cells of the same color which are four rook steps apart be (a,b) and (a+2, b+2) respectively.
There is only one path to take between these two squares. Let this path be (a,b), (a,b+1), (a+1,b+1), (a+1,b+2) and (a+2,b+2) we can say (a,b+1) is B otherwise we can interchange the rows and columns to be such that it is B.
Now let us look at the A cell vertically above which is (a,b+2) The only way the rook passes through it is via (a-1,b+2), (a,b+2) and(a,b+3) in this order. Hence to connect these two parts of the path, there must be a path connecting the cell (a,b+3) and (a,b) and also a path connecting (a+2,b+2) and (a-1,b+2)
But these are opposite vertices of a quadrilateral and paths are outside so they must interesect. But an intersection is only possible if a cell is visited twice and this is a contradiction.
Hence the number of cells must be at most 4. (499^2 -1)
No comments:
Post a Comment