11.3. All cells of a square table $n \times n$ are numbered in some order with numbers from 1 to $n^{2}$. Petya makes moves according to the following rules. On the first move, he places a rook in any cell. On each subsequent move, Petya can either place a new rook in some cell or move a rook from a cell numbered $a$ horizontally or vertically to a cell with a number greater than $a$. Each time a rook lands in a cell, that cell is immediately colored; placing a rook on a colored cell is prohibited. What is the minimum number of rooks Petya will need to, regardless of the initial numbering, be able to color all the cells of the table in several moves?

(D. Khramov)
Answer: $n$.

Solution. We will show that $n$ rooks are sufficient. For this, note that one rook is enough for each row: it can be placed in the cell of the row with the smallest number, and then visit all the cells of the row in increasing order of their numbers.

On the other hand, we will show that fewer than $n$ rooks may not be enough. For this, we number the cells so that the cells of one diagonal are numbered $1, 2, \ldots, n$ (the other cells are numbered arbitrarily). Then one rook cannot visit two cells of this diagonal: if the rook stands on one of these cells, the next move must be to a cell with a number greater than $n$, and thus, after that, it will not be able to return to the diagonal.

Finally, since a rook must visit each cell of the diagonal, Petya will have to use at least $n$ rooks.

Comment. Only the answer - 0 points.

Considering particular cases - 0 points.

Proving only that $n$ rooks are always sufficient - 3 points.

Only providing an example showing that for each $n$, at least $n$ rooks may be required - 3 points.