Solution to Problem #1

Solutions were provided by Chris Welty of London (England), Mario Roederer of Bethesda MD, Doug Magnoli of Pleasanton CA, Robin Stokes of the University of New England (Australia), Matt Hudelson of Washington State University, Arseniy Jidkov of Springfield MO, and Philippe Fondanaiche of Paris (France). Here is Chris Welty's solution:

Consider the first N integers arranged in a circle. We want to maximize
the sum of products of adjacent numbers ("Sopoan").

Suppose we have N integers arranged in a circle, and consider the "swap"
defined as follows: Take a selection of connected integers, with the
first being a and the last being b. Let A be the integer before a, and B
be the integer after b (so A and B are not in the selection). Reverse
the order of the integers in the selection. The only adjacent pairs of
integers that change are (a,A) and (b,B) become (a,B) and (b,A);
therefore the Sopoan has changed by aB+bA-aA-bB = (a-b)(B-A). The Sopoan
increases if the lower of (a,b) was next to the higher of (A,B) and
decreases otherwise.

Part I: What is the arrangement of N integers that maximizes the Sopoan?

Suppose 2 is not next to 1. Then we can make a swap so that 2 is next to
1, and this will increase the Sopoan. So the maximal solution must have
2 next to 1. Similarly 3 must be next to 1, 4 must be next to 2, 5 next
to 3, and the strand builds up so that the odd numbers are all on one
side of 1 in increasing order, the even numbers all on the other side
also in increasing order.

Part II: What is a formula for the maximal Sopoan?

If we know the formula for the first N-1 integers, and noticing that the
difference between the solution for N and the solution for N-1 is that N
has been inserted inserted between N-1 and N-2, the increase in the max
Sopoan is N(N-1)+N(N-2)-(N-1)(N-2)=N^2-2. We can then prove by induction
that the formula for the max Sopoan is (2n^3+3n^2-11n+18)/6 (valid for
N>1).

Part III: What is the arrangement that minimizes the Sopoan?

Suppose N is not next to 1, then we can make a swap so that N is next to
1 which decreases the sopoan. Similarly N-1 must be next to 1, 2 next to
N, 3 next to N-1, N-2 next to 2, N-3 next to 3, and we alternate high
and low numbers as we move away from 1. On one side we have low even
integers and N-even high integers, on the other low odd integers and
N-odd high integers.

Part IV: What is a formula for the minimal Sopoan?

For N odd, (N^3 + 3N^2 + 5N - 3)/6
For N even, (N^3 + 3N^2 + 5N - 6)/6

Back to the Archives

Back to the Math Department Homepage.