The cells of a 5x5 square grid is numbered by the positive integers from 1 to 25 inclusively, with each number occurring in a cell exactly once.
Prove that there must exist two adjacent cells with common edge (not including diagonally) whose numbers have an absolute difference of at least 5.
In general with the numbers 1, 2,...., n2 written on the cells of a nxn square grid in a random order such that each number occurs in a cell exactly once, will there always exist two adjacent cells with common edge (not including diagonally) whose numbers have an absolute difference of at least n, for every value of n ≥ 2?
The problem
Close Neighbors is very similar, but it has the addition of diagonal neighbors. I tried adapting the relatively simple solution to that problem and got this almost-a-solution.
Find the cells with 1 and n^2. If they are in the same row or column then the solution to Close Neighbors applies and resolves this case.
Otherwise there are two rows and two columns to examine. Call the row and column with '1' r1 and c1. Similarly, call the row and column with 'n^2' r2 and c2.
Traveling along a row there are two ways to go from c1 to c2, when wraparound is included. Choose the shorter way, the number of steps is at most n/2. Similarly there is a way to step from r1 to r2 in at most n/2 steps.
The combination of these two paths is a path from 1 to n^2 in at most n steps. If the largest difference is at most n-1 then the increments could total at most n^2-n, which is less than the n^2-1 needed. Therefore there must be a difference of at least n along this path.
I call this an almost-a-solution because of the clause when wraparound is included. The problem as stated does not allow for this variation.
Almost a solution
