Browse · MathNet
PrintIMO Problem Shortlist
counting and probability
Problem
On a 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 nonintersecting route of the limp rook consists of a sequence of pairwise different 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 first square of the route and start over. How many squares does the longest possible cyclic, non-intersecting route of a limp rook visit?
Solution
The answer is squares.
First we show that this number is an upper bound for the number of cells a limp rook can visit. To do this we color the cells with four colors and in the following way: for use , for use , for use and for use . From an -cell the rook has to move to a -cell or a -cell. In the first case, the order of the colors of the cells visited is given by , in the second case it is . Since the route is closed it must contain the same number of cells of each color. There are only -cells. In the following we will show that the rook cannot visit all the -cells on its route and hence the maximum possible number of cells in a route is .
Assume that the route passes through every single -cell. Color the -cells in black and white in a chessboard manner, i.e. color any two -cells at distance 2 in different color. Since the number of -cells is odd the rook cannot always alternate between visiting black and white -cells along its route. Hence there are two -cells of the same color which are four rook-steps apart that are visited directly one after the other. Let these two -cells have row and column numbers and respectively.
There is up to reflection only one way the rook can take from to . Let this way be . Also let without loss of generality the color of the cell be (otherwise change the roles of columns and rows).
Now consider the -cell . The only way the rook can pass through it is via in this order, since according to our assumption after every -cell the rook passes through a -cell. Hence, to connect these two parts of the path, there must be a path connecting the cell and and also a path connecting and .
But these four cells are opposite vertices of a convex quadrilateral and the paths are outside of that quadrilateral and hence they must intersect. This is due to the following fact: The path from to together with the line segment joining these two cells form a closed loop that has one of the cells and in its inside and the other one on the outside. Thus the path between these two points must cross the previous path.
But an intersection is only possible if a cell is visited twice. This is a contradiction.
Hence the number of cells visited is at most .
The following picture indicates a recursive construction for all -chessboards with mod 4 which clearly yields a path that misses exactly one -cell (marked with a dot, the center cell of the -chessboard) and hence, in the case of crosses exactly cells.
First we show that this number is an upper bound for the number of cells a limp rook can visit. To do this we color the cells with four colors and in the following way: for use , for use , for use and for use . From an -cell the rook has to move to a -cell or a -cell. In the first case, the order of the colors of the cells visited is given by , in the second case it is . Since the route is closed it must contain the same number of cells of each color. There are only -cells. In the following we will show that the rook cannot visit all the -cells on its route and hence the maximum possible number of cells in a route is .
Assume that the route passes through every single -cell. Color the -cells in black and white in a chessboard manner, i.e. color any two -cells at distance 2 in different color. Since the number of -cells is odd the rook cannot always alternate between visiting black and white -cells along its route. Hence there are two -cells of the same color which are four rook-steps apart that are visited directly one after the other. Let these two -cells have row and column numbers and respectively.
There is up to reflection only one way the rook can take from to . Let this way be . Also let without loss of generality the color of the cell be (otherwise change the roles of columns and rows).
Now consider the -cell . The only way the rook can pass through it is via in this order, since according to our assumption after every -cell the rook passes through a -cell. Hence, to connect these two parts of the path, there must be a path connecting the cell and and also a path connecting and .
But these four cells are opposite vertices of a convex quadrilateral and the paths are outside of that quadrilateral and hence they must intersect. This is due to the following fact: The path from to together with the line segment joining these two cells form a closed loop that has one of the cells and in its inside and the other one on the outside. Thus the path between these two points must cross the previous path.
But an intersection is only possible if a cell is visited twice. This is a contradiction.
Hence the number of cells visited is at most .
The following picture indicates a recursive construction for all -chessboards with mod 4 which clearly yields a path that misses exactly one -cell (marked with a dot, the center cell of the -chessboard) and hence, in the case of crosses exactly cells.
Final answer
996000
Techniques
Coloring schemes, extremal argumentsInvariants / monovariantsRecursion, bijection