Numbers written into a square grid

Question

I was working on a problem from The Art and Craft of Problem Solving by Zietz, in the chapter called 'The extreme principle.' Here is the problem:

"The integers from 1 to $n^2$ are written into a nxn grid, no overlapping. Prove that there exists two adjacent cells whose numbers have difference at least n+1. Adjacent means touching horizontally, vertically, or diagonally."

I tried to consider the largest difference and assume that it was less than n+1, then add all possible differences together but this doesn't lead me to a contradiction when I try to put bounds on the rest of the differences. How do I approach this problem?

(I'm on my phone so I apologize if these tags are not relevant)

Answer 1

Hints:

• What is the difference between the extreme values in the square?

• What is the upper bound on the number of (horizontal, vertical or diagonal) steps between them on the shortest route between the extreme values?

• What is the lower bound on the average difference per step on the shortest route between the extreme values?