ITOT 43 Spring 2022 - THPT A - additive practice Question 4

A rook traverses an $n\times n$ board, each move to an edge-adjacent cell, visiting each cell exactly once. Bob writes the integers 1 through $n^2$ in the order of the visits. Let $M$ be the largest absolute difference between numbers in any two edge-adjacent cells. What is the smallest possible value of $M$? (8 points)



Neutral editorial illustration.