Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer 1

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!

share|improve this answer
2  
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 '12 at 16:58
    
This suggests a general procedure to make a constructive proof into a proof by contradiction ;-) –  Pietro Majer May 29 '12 at 6:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.