Each cell in an $n \times n$ table is filled with an integer from 1 to $n^2$ without repetition. It is known that the number $1$ does not lie along the border. Prove that there exist two adjacent cells (cells with a common vertex or common side) such that the difference between the two numbers is at least $n+3$.
I was able to prove that the difference would be at least $n+1$, see below:
We assume that the difference between two adjacent cells is less than $n+1$.
If we place a counter on the cell numbered $1$, the counter will have to move through at most $n-1$ cells to reach the cell numbered $n$.
The difference between the numbers in adjacent squares is less than $n+1$. The counter moves through at most $n-1$ cells, and the difference between adjacent grids is less than $n+1$, therefore the difference between $n^2$ and $1$ would be appear to be less than $(n-1)(n+1) = n^2-1$. This is a contradiction, and therefore the difference between two adjacent cells has to be at least $n+1$
: I've proved that the difference between adjacent cells has to be at least $n+1$ (is the proof foolproof though), however, I need to prove that the there exist two adjacent cells such that the difference between the numbers in those two cells is $n+3$. Did I miss something in my proof? I do not know how to include the requirement that '$1$' does not lie along the border of the cell.
Thanks in advance
Best Answer
This construction is exactly the right idea, but your bounds can be further refined. You know the cell containing $1$ is not on the edge, so only $n-2$ cells will need to be traversed. You can therefore assume the difference between adjacent cells is no more than $n+2$ and arrive at a contradiction.