Playing with numbers form $1$ to $n^2$ in an $n\times n$ grid

Suppose we write each number from $1$ to $n^2$ in an $n\times n$ grid exactly once. Prove there are two adjacent cells such that the absolute value of their difference is not less than $n$.

I think it should be a pigeonhole problem, but the work I did so far was basic observations like if we assume all differences are less than $n$, then neither of $1,2,\dots,2n-2$ could be in the row or the column $n^2$ is placed.

Any hints would be appreciated.

Solution 1:

For $1 \leq k \leq n^2$, let $S_k$ be the $k$-element set of cells that contain the numbers $1$, $2$, ..., $k$. Choose the minimal $k$ such that $S_k$ either contains one cell in each row or one cell in each column. Without loss of generality, assume that $S_k$ contains one cell in each column. Note that $S_k$ cannot contain a full column, since this would contradict the minimality of $k$. Therefore, each column contains at least one cell in $S_k$ and at least one cell not in $S_k$. This means that each column contains a cell of $S_k$ that borders a cell outside $S_k$. Let $a_i$ and $b_i$ be numbers in column $i$ such that $a_i$ lies in a cell from $S_k$ and $b_i$ lies in a neighboring cell outside $S_k$. Then the $a_i$ are different numbers from $\{1,2,\ldots,k\}$, so $\min(a_i)$ is at most $k+1-n$. We then have $b_i - a_i \geq k+1 - (k+1-n) = n$, so column $i$ contains two cells whose entries differ by at least $n$.

Example:

$$ \begin{matrix} {\color{red}1} & {\color{red}2} & {\color{red}6} & {\color{blue}1\color{blue}1} \\ {\color{red}3} & {\color{blue}8} & {\color{red}5} & {\color{red}7} \\ {\color{red}4} & 13 & {\color{blue}9} & {\color{blue}1\color{blue}6} \\ {\color{blue}1\color{blue}5} & 12 & 10 & 14 \end{matrix} $$

In this example $n=4$ and $k=7$ (note that each column contains one of the numbers $1$, $2$, ..., $7$). Each column contains a number that is $\leq 7$ bordering a number that is $\geq 8$.

The bound is sharp: it is attained in the example where cell $(i,j)$ contains the number $(i-1)n + j$.