Maths Olympiad Prep

Library / /15 of 15

Algebra Difficulty 8.6 Shortlist Prove it Romania

Given an integer n2n \ge 2, determine the maximum value the sum
a1/a2+a2/a3++an1/an a_1/a_2 + a_2/a_3 + \dots + a_{n-1}/a_n
may achieve, and the points at which the maximum is achieved, as a1,,ana_1, \dots, a_n run over all of positive real numbers subject to
aka1++ak1,k=2,,n. a_k \ge a_1 + \dots + a_{k-1}, \quad k = 2, \dots, n.

Solution

First solution. The required maximum is n/2n/2 and is achieved if and only if ak=2k2a1a_k = 2^{k-2}a_1, k=2,,nk = 2, \dots, n, and a1a_1 is any positive real number.
To prove this, let Ak=a1++akA_k = a_1 + \dots + a_k, k=0,,n1k = 0, \dots, n-1, where empty sums are zero, and refer to the condition in the statement, Akak+1A_k \le a_{k+1}, k=0,,n1k = 0, \dots, n-1, to write
k=1n1akak+1=k=1n1AkAk1ak+1=k=1n2Ak(1ak+11ak+2)+An1ank=1n2ak+1(1ak+11ak+2)+1=k=1n2(1ak+1ak+2)+1=n1+a1a2k=1n1akak+1nk=1n1akak+1. \begin{align*} \sum_{k=1}^{n-1} \frac{a_k}{a_{k+1}} &= \sum_{k=1}^{n-1} \frac{A_k - A_{k-1}}{a_{k+1}} = \sum_{k=1}^{n-2} A_k \left( \frac{1}{a_{k+1}} - \frac{1}{a_{k+2}} \right) + \frac{A_{n-1}}{a_n} \\ &\le \sum_{k=1}^{n-2} a_{k+1} \left( \frac{1}{a_{k+1}} - \frac{1}{a_{k+2}} \right) + 1 = \sum_{k=1}^{n-2} \left( 1 - \frac{a_{k+1}}{a_{k+2}} \right) + 1 \\ &= n - 1 + \frac{a_1}{a_2} - \sum_{k=1}^{n-1} \frac{a_k}{a_{k+1}} \le n - \sum_{k=1}^{n-1} \frac{a_k}{a_{k+1}}. \end{align*}
Consequently, k=1n1ak/ak+1n/2\sum_{k=1}^{n-1} a_k / a_{k+1} \le n/2, and equality holds if and only if Ak=ak+1A_k = a_{k+1}, k=1,,n1k = 1, \dots, n-1, which is clearly the case if and only if ak=2k2a1a_k = 2^{k-2}a_1, k=2,,nk = 2, \dots, n, and a1a_1 is any positive real number.

Second solution. We now show by induction on n2n \ge 2 that sn(a1,,an)=a1/a2+a2/a3++an1/ann/2s_n(a_1, \dots, a_n) = a_1/a_2 + a_2/a_3 + \dots + a_{n-1}/a_n \le n/2 for all positive real numbers a1,,ana_1, \dots, a_n such that aka1++ak1a_k \ge a_1 + \dots + a_{k-1}, k=2,,nk = 2, \dots, n, and equality holds if and only if ak=2k2a1a_k = 2^{k-2}a_1, k=2,,nk = 2, \dots, n, and a1a_1 is any positive real number.
Clearly, s2(a1,a2)1s_2(a_1, a_2) \le 1 if 0<a1a20 < a_1 \le a_2, and s3(a1,a2,a3)s3(a1,a2,a1+a2)3/2s_3(a_1, a_2, a_3) \le s_3(a_1, a_2, a_1+a_2) \le 3/2 if 0<a1a20 < a_1 \le a_2 and a1+a2a3a_1 + a_2 \le a_3; in both cases, equality holds if and only if the aka_k are as stated.
Now let n4n \ge 4, let a1,,ana_1, \dots, a_n be positive real numbers such that aka1++ak1a_k \ge a_1 + \dots + a_{k-1}, k=2,,nk = 2, \dots, n, and write
sn(a1,,an)sn(a1,,an1,a1++an1)=sn2(a1,,an2)+an2an1+an1a1++an1. \begin{align*} s_n(a_1, \dots, a_n) &\le s_n(a_1, \dots, a_{n-1}, a_1 + \dots + a_{n-1}) \\ &= s_{n-2}(a_1, \dots, a_{n-2}) + \frac{a_{n-2}}{a_{n-1}} + \frac{a_{n-1}}{a_1 + \dots + a_{n-1}}. \end{align*}
If we show that
an2an1+an1a1++an1an2a1++an2+12,() \frac{a_{n-2}}{a_{n-1}} + \frac{a_{n-1}}{a_1 + \cdots + a_{n-1}} \le \frac{a_{n-2}}{a_1 + \cdots + a_{n-2}} + \frac{1}{2}, \quad (*)
then sn(a1,,an)sn1(a1,,an2,a1++an2)+1/2(n1)/2+1/2=n/2s_n(a_1, \dots, a_n) \le s_{n-1}(a_1, \dots, a_{n-2}, a_1 + \dots + a_{n-2}) + 1/2 \le (n-1)/2 + 1/2 = n/2, by the induction hypothesis; the cases of equality also follow from the induction hypothesis.
Finally, to establish (*), simply notice that the numerator of the right-hand member and the left-hand member is the product of an1a1an20a_{n-1} - a_1 - \dots - a_{n-2} \ge 0 and an1(an2a1an3)+2an2(a1++an2)2an2(a1++an2)>0a_{n-1}(a_{n-2} - a_1 - \dots - a_{n-3}) + 2a_{n-2}(a_1 + \dots + a_{n-2}) \ge 2a_{n-2}(a_1 + \dots + a_{n-2}) > 0.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.