6. (B. Frenkin) A rook has traversed an $n \times n$ board, visiting each cell exactly once, with each move being exactly one cell. The cells are numbered from 1 to $n^{2}$ in the order of the rook's traversal. Let $M$ be the maximum difference between the numbers of adjacent (by side) cells. What is the smallest possible value of $M$?
Solution: Answer: $2 N-1$.

Example: traverse the board in a "snake" pattern, starting from the bottom left corner: to the right to the end, up by 1, to the left to the end, up by 1, ...

Estimate: Assume the opposite: $MB$ (by columns), on the other hand, $A<B$ (by rows). Contradiction