Suppose that the n^2$n^2$ cells of an nxn$n\times n$ array are labeled with the integers 1, ..$1, \dots, n^2$., n^2, going Under the traditional left-to-right and top-to-bottom. Then labeling, the labels of horizontally adjacent cells differ by 1$1$, and the labels of vertically adjacent cells differ by n$n$. Is it possible to relabel the array so that the labels of adjacent cells (horizontally or vertically) differ by less than n$n$?
I suspect the answer is "no" but do not have a proof. I made up this problem while contemplating a similar Putnam Competition problem (1981, A-2). In this problem, adjacent cells are horizontal, vertical, or diagonal neighbors.
