# Labeling a Square Array

Suppose that the $n^2$ cells of an $n\times n$ array are labeled with the integers $1, \dots, n^2$. Under the traditional left-to-right and top-to-bottom labeling, the labels of horizontally adjacent cells differ by $1$, and the labels of vertically adjacent cells differ by $n$. Is it possible to relabel the array so that the labels of adjacent cells (horizontally or vertically) differ by less than $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.

-
The folks that organize elementary math competitions are always eager to find "nice" problems of this kind for the contests. The next time you find such a nice one, consider proposing it for a math competition instead of "spoiling it" by posting it on the internet. :) – Federico Poloni Feb 13 '12 at 14:24
@F.Poloni: I sympathize, but M.Erickson's question is so natural a variation of that 1981 Putnam problem that 30+ years later it could hardly be new. – Noam D. Elkies Feb 13 '12 at 15:08

Suppose such a labeling exists. Let $F_k$ the region formed by the cells labeled $\{1,2,\dots,k\}$. There is a minimum $k>1$ such that $F_k$ connects two opposite sides of the checkerboard (wlog suppose left and right side). Color in black the cells belonging to $F_{k-1}$, and in white the rest.
Then, $k$ is in a white cell touching a black cell, and in every other column there is at least one black and one white cell. So overall there are at least $n$ white cells touching black cells (one per column). One of them must contain a number $\geq k-1+n$, and (since it touches the black region) it touches a number $\leq k-1$. Contradiction!