7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. :) $\endgroup$ Feb 13, 2012 at 14:24
  • $\begingroup$ @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. $\endgroup$ Feb 13, 2012 at 15:08

1 Answer 1

10
$\begingroup$

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!

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ Feb 13, 2012 at 16:58
  • $\begingroup$ This suggests a general procedure to make a constructive proof into a proof by contradiction ;-) $\endgroup$ May 29, 2012 at 6:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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