Kvant Math Problem 1321
For small boards the bound looks plausible.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m34s
Source on kvant.digital
Problem
A rook has visited every square on a chessboard of size $n\times n$ squares. Prove that in doing so it must have changed the direction of its movement at least $2n-2$ times. (The rook moves parallel to the sides of the square.)
Yu. Khodzinsky, 10th-grade student
Exploration
For small boards the bound looks plausible. On a $2\times2$ board, every route visiting all four squares must turn at least twice. The claimed lower bound is $2n-2=2$.
A change of direction means a switch between horizontal and vertical motion. The rook's path consists of maximal straight segments. If there are $T$ changes of direction, then there are $T+1$ such segments.
The board has $n$ rows and $n$ columns. A horizontal segment lies entirely in one row, and a vertical segment lies entirely in one column. If a row contains a visited square, then some horizontal segment must lie in that row, because a vertical move alone cannot visit more than one square of a row. Since every square is visited, every row contains visited squares. Thus every row must contain at least one horizontal segment. By the same reasoning every column must contain at least one vertical segment.
This suggests counting rows and columns touched by straight segments. If there are too few segments, perhaps there are not enough horizontal segments to cover all rows and enough vertical segments to cover all columns simultaneously.
Suppose there are $T$ turns. Then there are $T+1$ segments. Consecutive segments alternate orientation. Hence the numbers of horizontal and vertical segments differ by at most $1$. To cover all $n$ rows, there must be at least $n$ horizontal segments. To cover all $n$ columns, there must be at least $n$ vertical segments. Therefore there must be at least $2n$ segments altogether. This yields $T+1\ge 2n$, hence $T\ge 2n-1$.
This is stronger than the required bound $T\ge 2n-2$. The only point needing careful justification is the statement that every row requires a horizontal segment and every column requires a vertical segment. A careless argument could overlook the possibility that a row is visited only at isolated points reached by vertical moves. But if every square of the row is visited, then at least two squares of that row are visited when $n\ge2$, and a vertical segment cannot connect distinct squares within the same row. Some horizontal movement in that row is unavoidable.
The strongest formulation is: each row must contain a horizontal segment because all $n$ squares of that row are visited; similarly for columns.
Problem Understanding
We are given a rook's route on an $n\times n$ chessboard. The rook moves only horizontally or vertically from square to square and eventually visits every square of the board. We must prove that the number of times the rook changes between horizontal and vertical motion is at least $2n-2$.
This is a Type B problem. We must prove a universal lower bound.
The core difficulty is to convert the geometric condition that every square is visited into a combinatorial statement about the straight segments of the route.
Proof Architecture
Let $T$ be the number of changes of direction, and decompose the route into maximal straight segments.
Lemma 1. Every row of the board contains at least one horizontal segment of the route. Sketch: all squares of the row are visited, and vertical motion alone cannot account for movement between different squares of the same row.
Lemma 2. Every column of the board contains at least one vertical segment of the route. Sketch: the same argument applied to columns.
Lemma 3. If the route has $s$ maximal straight segments, then the numbers of horizontal and vertical segments differ by at most $1$. Sketch: orientations alternate along the route.
Lemma 4. The route has at least $2n$ maximal straight segments. Sketch: by Lemmas 1 and 2 there are at least $n$ horizontal and at least $n$ vertical segments.
The hardest point is Lemma 1, because it must exclude the possibility that a row is visited entirely through vertical passages without any horizontal segment lying in that row.
Solution
Let $T$ be the number of changes of direction made by the rook. Decompose the route into maximal straight segments. If the route contains $s$ such segments, then
$$s=T+1.$$
Each segment is either horizontal or vertical, and consecutive segments have different orientations.
We first show that every row contains a horizontal segment.
Fix a row. Since the rook has visited every square of the board, it has visited all $n$ squares of this row. Consider two adjacent squares of the row. To visit both of them, the route must at some moment move from one square of the row to the other. Such a move is horizontal and lies entirely in the chosen row. Hence the row contains a horizontal segment.
Since there are $n$ rows, there are at least $n$ horizontal segments altogether. Indeed, a horizontal segment lies in a single row, and every row contains at least one horizontal segment.
Applying the same argument to columns, every column contains a vertical segment. Therefore there are at least $n$ vertical segments altogether.
Let $h$ be the number of horizontal segments and $v$ the number of vertical segments. Then
$$h\ge n,\qquad v\ge n.$$
Hence
$$s=h+v\ge 2n.$$
Since $s=T+1$, we obtain
$$T+1\ge 2n,$$
so
$$T\ge 2n-1.$$
In particular,
$$T\ge 2n-2.$$
Thus the rook must change the direction of its movement at least $2n-2$ times.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is proving that every row contains a horizontal segment. Suppose a row contained no horizontal segment. Then every time the rook entered that row, it would leave immediately along the same column, because all motion within the row would be forbidden. The rook could then visit at most one square of that row during each passage. Since all $n$ squares of the row must be visited, some movement between squares of the row is necessary, and that movement is horizontal. The contradiction confirms the claim.
The second delicate step is the passage from row and column coverage to the inequality $h+v\ge 2n$. A horizontal segment belongs to exactly one row, so one segment cannot simultaneously satisfy the requirement for two different rows. Thus at least $n$ horizontal segments are needed. The same reasoning gives at least $n$ vertical segments. Adding the inequalities is legitimate because horizontal and vertical segments are disjoint classes.
The third delicate step is relating turns to segments. If there are no turns, there is one segment. Each additional turn starts exactly one new maximal straight segment. Hence $s=T+1$.
Alternative Approaches
Another proof views the route as an alternating sequence of horizontal and vertical segments. Let $h$ and $v$ be their numbers. Every row must contain an edge of the route joining two neighboring squares in that row, so $h\ge n$. Every column must contain an edge joining two neighboring squares in that column, so $v\ge n$. Since the number of turns equals $h+v-1$, the estimate
$$T=h+v-1\ge 2n-1$$
follows immediately.
The main proof is preferable because it works directly with maximal straight segments and makes the connection between turns and segments completely explicit.