Put the numbers 1 through 8 into the boxes of this diagram so that no two consecutive numbers are in boxes...

combinatorics/no.consecutive.neighbors New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

Put the numbers 1 through 8 into the boxes of this diagram so that no
two consecutive numbers are in boxes that touch, not even at a corner:

                _____
             __|__|__|__
            |__|__|__|__|
               |__|__|

Show solution

In article <19971105181101.NAA00742@ladder02.news.aol.com>, DonC97
<donc97@aol.com> wrote:
>Note my last attempt:
>
>                  6 3
>                2 8 1 7
>                  4 5
>
>I would have made it, except the 4 and 5 touched.

Yes it can, and uniquely up to diagram symmetries.  It's an old puzzle.

The key is the two center squares: each touches all but one of the
others, so must be occupied by a number to which only one other number
is consecutive; i.e. 1 or 8.  So 1 and 8 must be in the center,
and their numerical neighbors 2 and 7 must be opposite them --
as they are in your near-solution.  It is easy then to check
that the remaining numbers 3-6 must be placed thus:

                  5 3
                2 8 1 7
                  6 4

or the same reflected about the horizontal axis.

ObPuzzle: note that symmetrically placed numbers add up to 9; explain.

-- Noam D. Elkies <elkies@math.harvard.edu>