B3. There are n terms to be added, each at most n(n-1), so we cannot
exceed a cubic function of n. In fact, the maximum value (if my
calculations are correct) is P(n) = (2n^3-3n^2-11n+72)/6 for n>=3.
(P(2)=2.)
Observe that the "circular sum" in question is determined by the
ordered set {x_1=1, ..., x_n=n} and the permutation f used to write
the sum as
x_f(1) * x_f(2) + x_f(2) * x_f(3) + ... + x_f(n) * x_f(1).
In particular, with fixed x_i, there are only as many sums to
consider as there are permutations, and so there is a maximum. It
does not occur for a unique f (indeed, the circular sum is really
a function of the coset of <(1 2 ... n)> to which f belongs),
but it's essentially unique, as we will see by construction.
In particular, we will see that the optimal circular sum involves
the product x_1*x_2 .
For n=2,3, there is really only one circular sum
x_1 x_2 and
x_1 x_2 + x_2 x_3 + x_3 x_1
respectively. With the given values of x_i these equal P(2)=2 and
P(3)=11 respectively.
So now by induction suppose that for any permutation of {1, 2, ..., n-1}
we know the circular sum to be no larger than P(n-1). I claim that
the maximum value of a circular sum for {x_1=2, x_2=3, ..., x_(n-1)=n}
is then P(n-1) + n(n-1) + (n-1). Indeed, for any permutation f of these
terms, we relate the circular sum for the x_i to the corresponding sum
for the y_i=x_i-1 (={1, 2, ..., n-1}): by expanding the former we get
y_f(1) * y_f(2) + y_f(2) * y_f(3) + ... + y_f(n) * y_f(1)
+ 2 * (y_1+...+y_(n-1))*1 + (n-1)*1^2
which is the latter's circular sum plus 2*Sum( i, i=1..n-1 ) + (n-1).
[The factor "2" here is absent when n-1 = 2].
By induction, that circular sum is at most P(n-1). Note that by induction
we have the additional information that the optimal circular sum of
the x_i includes x_1*x_2 = 2*3 as a summand.
Now suppose an (optimal) permutation for {1, 2, ..., n} is selected.
Writing x and y for the terms multiplying 1, we see the circular
sum C is
C = 1*x+ 1*y - x*y + S
where S is a circular sum of {2, 3, ..., n} formed by adding x*y
to the sum of all terms in C not having 1 as a factor. (That is, we
"remove the 1 and close the loop".) Since this may be written
C = 1 - (x-1)*(y-1) + S,
it is clear that C <= 1 - (2-1)*(3-1) + max(S), the last term being
the maximum (over all permutations of {2,3,..., n}) of the circular
product involving those n-1 numbers.
By an earlier paragraph, we know that this maximum is
P(n-1) + (n+1)*(n-1). This gives an upper bound of P(n-1) + (n^2-2)
to C.
Now, we would not know whether this upper bound were ever attained except that
we know the optimal circular sum for {2, 3, ..., n} does involve 2*3
as a summand. Thus, replacing this summand by 1*2+1*3 gives a circular
summand of {1, 2, ..., n} equal to the established upper bound.
It remains only to check that the recurrence relation
P(n)=P(n-1)+(n^2-2)
P(3)=11
has the solution
P(n) = (n^3-n)/3 - (n^2-n)/2 - 2n + 12 = (2n^3-3n^2-11n+72)/6,
which is elementary.
[djr - well, it would be if I kept my signs straight! Actually it comes out
to (2n^3+3n^2-11n+18)/6.]
NOTE: The optimal product may be found from this proof: it's
1*3 + 3*5 + 5*7 + ... (top odd)*(top even)+ ... + 8*6 + 6*4 + 4*2 + 2*1
Facebook
Twitter