IMO 1999 SL A6

Origin: SWE | Category: Algebra

Problem

For n \geq3 and a1 \leqa2 \leq\cdot \cdot \cdot \leqan given real numbers we have the following instructions: (1) place the numbers in some order in a circle; (2) delete one of the numbers from the circle; (3) if just two numbers are remaining in the circle, let S be the sum of these two numbers. Otherwise, if there are more than two num- bers in the circle, replace (x1, x2, x3, . . . , xp−1, xp) with (x1 + x2, x2 + x3, . . . , xp−1 + xp, xp + x1). Afterwards, start again with step (2). Show that the largest sum S that can result in this way is given by the formula Smax = n k=2 n −2 / k −1 ak.

Solution

We ﬁrst introduce some useful notation. An arrangement around the circle will be denoted by x = {x1, x2, . . . , xn}, where the elements are arranged clockwise and x1 is ﬁxed to be the smallest number. We will call an ar- rangement balanced if x1 \leqxn \leqx2 \leqxn−1 \leqx3 \leqxn−2 \leq\cdot \cdot \cdot (the string of inequalities continues until all the elements are accounted for). We will denote the permutation of x = {x1, x2, . . . , xn} in ascending order by x′ = {x′ 1, x′ 2, . . . , x′ n}. We will let fi(x) = {fi(x)1, fi(x)2, . . . , fi(x)n−1} denote the arrangement after one iteration of the algorithm where xi was the deleted element. Lemma 1. If an arrangement x is balanced, then f1(x) is also balanced. Proof. In one iteration we have {x1, . . . , xn} \to{xn + x2, x2 + x3, . . . , xn−1 + xn}. Since xn \leqx2 \leqxn−1 \leqx3 \leqxn−2 \leq\cdot \cdot \cdot , it follows that xn + x2 \leqxn + xn−1 \leqx2 + x3 \leqxn−1 + xn−2 \leq\cdot \cdot \cdot , which means that f1(x) is balanced. We will ﬁrst show by induction that Smax can be reached by using the bal- anced initial arrangement {a1, a3, a5, . . . , a6, a4, a2} and repeatedly delet- ing the smallest member. For n = 3 we have S3 = a2 + a3, in accordance with the formula. Assuming that the formula holds for a given n, we note that for an arrangement x = {a1, a3, a5, . . . , a6, a4, a2} the arrangement f1(x) is also balanced. We now apply the induction hypothesis and use that n−2 i + n−2 i−1

n−1 i : S(x) = S(f1(x))

n−1 k=2 n −2 [k/2] −1 (ak + ak+2) + n −2 [n/2] −1 (an + an+1) = Smax.

We now prove that every other arrangement yields a smaller value. We shall write {x1, . . . , xn} \leq{y1, . . . , yn} whenever x′ n + x′ n−1 + \cdot \cdot \cdot + x′ i \leq y′ n + y′ n−1 + \cdot \cdot \cdot + y′ i holds for all 1 \leqi \leqn. Lemma 2. Let x be an arbitrary arrangement and y a balanced arrange- ment, both of n elements, such that x \leqy. Then it follows that fi(x) \leqf1(y), for all i. Proof. For any 1 \leqj \leqn−1 there exists kj such that fi(x)j = xkj +xkj+1 (assuming kj + 1 = 1 if kj = n −1). Then we have fi(x)n−1 + \cdot \cdot \cdot + fi(x)n−j = (xk1 + xk1+1) + \cdot \cdot \cdot + (xkj + xkj+1) \leq2x′ n + \cdot \cdot \cdot + 2x′ n−i+1 + x′ n−i + x′ n−i−1 = f1(y)n−1 + \cdot \cdot \cdot + f1(y)n−j for all j, and hence fi(x) \leqf1(y). An immediate consequence of Lemma 2 is f n−2(x) \leqf n−2 (y), implying S = f n−2(x)1 + f n−2(x)2 \leqf n−2 (y)1 + f n−2 (y)2 = Smax(y). Thus the proof is ﬁnished.