Given real numbers x1 ≤ x2 ≤ ... ≤ xn (with n > 2), carry out the following procedure:
(1) arrange the numbers in a circle;
(2) delete one of the numbers;
(3) if just two numbers are left, then take their sum. Otherwise replace each number by the sum of it and the number on its right. Go to step 2.
Show that the largest sum that can be achieved by this procedure is (n-2)C0 x2 + (n-2)C0 x3 + (n-2)C1 x4 + (n-2)C1 x5 + (n-2)C2 x6 + ... + (n-2)C( [n/2]-1 ) xn, where mCk represents the binomial coefficient.
Solution
We show first that the sum given can be achieved by starting with the order x2, x4, x6, ... , xn, ... , x7, x5, x3, x1. [So we have the even numbers in increasing order, then the odd numbers in decreasing order.] We repeatedly delete the smallest number. We use induction on n.
For n = 3, we delete x1 and then take the sum as x2 + x3 = 1C0 x2 + 1C0 x3, as required. Now assume the result is true for n. Take n+1 numbers. After the first iteration, we have y2, y4, ... , yn, ... , y3, y1, where y1 = x2 + x3, xi = xi + xi+2 for i = 2, 3, ... , n-1 and xn = xn + xn+1. It is easy to check that y1 ≤ y2 ≤ ... ≤ yn.
Hence (by induction) the sum is ∑2n (n-2)C([k/2]-1) yk = y2 + y3 + (∑4n-1) + yn = x2 + x3 + (∑4n-1( (n-2)C( [k/2]-1) + (n-2)C( [k/2]-2) )xk ) + ( (n-2)C( [n/2]-1) + (n-2)C( [n/2] -2) ) xn = (n-1)C0 x2 + (n-1)C0 x3 + (∑4n (n-1)C( [k/2] - 1) xk ) + (n-1)C( [(n+1)/2] -1) xn+1 = ∑2n+1 (n-1)C( [k/2] - 1) xk, which establishes the result for n+1.
We define a partial order (see below) on n-tuples as follows. For any n-tuple (x1, ... , xn), let (x1', x2', ... , xn') denote the same elements arranged in increasing order. Then we define (x1, ... , xn) ≤ (y1, ... , yn) to mean that xi' + xi+1' + ... + xn' ≤ yi' + yi+1' + ... + yn' for i = 1, 2, ... , n.
We claim that if (x1, ... , xn) ≤ (y1, ... , yn) and y1 ≤ y2 ≤ ... ≤ yn, and (z1, ... , zn-1) is derived from (x1, ... , xn) by carrying out steps (1), (2), (3) (with no iteration, so we get a set of n-1 numbers), then (z1, ... , zn-1) ≤ (y2+y3, y2+y4, y3+y5, ... , yn-2+yn, yn-1+yn).
Notice that if the claim is true, then it follows immediately that the procedure described above gives the largest possible sum.
Partial orders
A total order has similar properties to the ordinary < relation. A partial order drops the requirement that for distinct x, y either x < y or y < x. The key property is transitivity: if x < y and y < z, then x < z. As with the familiar <, we use both < and ≤ (so < implies not equal, whereas ≤ allows equality).
© John Scholes
jscholes@kalva.demon.co.uk
10 Oct 2002
Last corrected/updated 22 Oct 2002