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.

Improve this question
$\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$
    – Federico Poloni
    Commented 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$
    – Noam D. Elkies
    Commented Feb 13, 2012 at 15:08

1 Answer 1

Reset to default
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!

Improve this answer
$\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$
    – Timothy Chow
    Commented Feb 13, 2012 at 16:58
  • $\begingroup$ This suggests a general procedure to make a constructive proof into a proof by contradiction ;-) $\endgroup$
    – Pietro Majer
    Commented May 29, 2012 at 6:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .