9.3. Given a natural number $n$. On a $2 n \times 2 n$ chessboard, $2 n$ rooks are placed such that no two rooks are in the same row or column. After that, the board is cut along the grid lines into two connected parts, symmetric to each other with respect to the center of the board. What is the maximum number of rooks that could end up in one of the parts? (A grid figure is called connected if, from any cell of this figure, you can reach any other cell by moving to an adjacent cell each time.)

(D. Khramiov)
Answer: $2 n-1$.

Solution: Note that in each column and each row, there is exactly one rook.

First, we show that all $2 n$ rooks could not have ended up in one part. Let $A, B, C, D$ be the corner cells of the board (in counterclockwise order, see Fig. 2). By symmetry, $A$ and $C$ must belong to different parts, as must $B$ and $D$. This means that either $A$ and $B$, or $A$ and $D$ lie in the same part, while the other two cells lie in the other part.

Suppose, for definiteness, that $A$ and $B$ lie in part I. Then all the boundary cells between them must also lie in part I; indeed, if some such cell $X$ lies in part II, then some path from $X$ to $C$ lies in part II, and some path from $A$ to $B$ lies in part I; but these paths must have a common cell, which is impossible.

Thus, the entire row between cells $A$ and $B$ lies in part I, meaning it must contain at least one rook. Similarly, part II also has an entire row (between $C$ and $D$), and thus contains a rook. This leads to the required result.

It remains to provide an example where $2 n-1$ rooks are located in one of the parts. One possible

![](https://cdn.mathpix.com/cropped/2024_05_06_97947114d3ba6c13bc6bg-5.jpg?height=414&width=420&top_left_y=972&top_left_x=872)

Fig. 2 example is constructed as follows. Consider the diagonal of the square; the cells below it, as well as the lower half of the diagonal itself, will fall into one part; the remaining cells will fall into the second part. Place $2 n-1$ rooks in the cells immediately below the diagonal; then they will be in one part. Place the remaining rook at the intersection of the remaining row and column. Fig. 2 shows such an example for $n=5$.

Remark. The key consideration in the estimate is the following: If four boundary cells $P, Q, R$, $S$ are marked in order, then any path between $P$ and $R$ has a common cell with any path between $Q$ and $S$.

Using this statement, the estimate can be conducted differently. For example, by symmetry, there are $4 n$ boundary segments of the board belonging to one part, and $4 n$ belonging to the other. From the above consideration, each set of $4 n$ segments forms a group of consecutive segments; thus, among them there is an entire side, and we again obtain that each part contains one of the boundary lines (vertical or horizontal).

Comment. Only the answer - 0 points.

Only an example where $2 n-1$ rooks are in one part - 2 points.

Only the estimate proving that $2 n$ rooks cannot be in one part - 5 points.

The consideration highlighted in italics in the comment above is accepted without proof.