## 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 2012 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 2012 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!

-
Nice argument. It is a matter of taste, but I would recommend removing "Suppose such a labeling exists" and "Contradiction" since they don't add anything to the argument. – Timothy Chow Feb 13 2012 at 16:58
This suggests a general procedure to make a constructive proof into a proof by contradiction ;-) – Pietro Majer May 29 at 6:16