writing down minimum and maximum cyclical permutations

[Brendan McKay]

* Brendan McKay <bdm at cs.anu.edu.au> [050201 18:12]:
> * Eugene McDonnell <eemcd at mac.com> [050201 17:41]:
> > maximum odd
> > 2 4 6 - - - -
> > - - - 7 5 3 1
> > 2 4 6 7 5 3 1
> > 
> > maximum even
> > 1 3 5 7 - - - -
> > - - - - 8 6 4 2
> > 1 3 5 7 8 6 4 2

Let's prove it. First a general remark: very many optimization
problems concerned with arrangements can be solved by considering
what happens to an optimum solution when you perturb it slightly.

So let
  X = ..>... A B ...>...>... C D ...>..
give the maximum value (cyclic case).  A,B,C,D are distinct
elements in the configuration shown.

Now turn around the section from B to C:
  Y = ..>... A C ...<...<... B D ...>..
The change to the sum of adjacent products is
  X - Y = (AB+CD)-(AC+BD) = (A-D)(B-C).
Since X is the maximum, X-Y must be positive, so
 sign(A-D) = sign(B-C)     (*).

It turns out that condition (*) is strong enough to give
a unique solution up to rotation and reflection.

Suppose 2 is not adjacent to 1, then we can find
  .... 1 B ... 2 D ...
which violates (*) since sign(1-D) is not equal to sign(B-2).
Therefore 2 is adjacent to 1.

By the same technique, 3 is also adjacent to 1, then 4 is 
adjacent to 2, then 5 is adjacent to 3, etc etc until the
solutions Eugene depicted above are obtained.  QED/

I haven't tried it, but I bet the same method also works
for the minimum and for both the maximum and minimum in
the non-cyclic case.

Cheers, Brendan.