Maths Olympiad Prep

Library / Romania — NMO Selection Tests for the Balkan and International Mathematical Olympiads /69 of 80

Romania — NMO Selection Tests for the Balkan and International Mathematical Olympiads

Algebra Difficulty 8.6 Shortlist Prove it Romania

Given an integer n≥2n \ge 2, determine the maximum value the sum
a1/a2+a2/a3+⋯+an−1/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
ak≥a1+⋯+ak−1,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=2k−2a1a_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,…,n−1k = 0, \dots, n-1, where empty sums are zero, and refer to the condition in the statement, Ak≤ak+1A_k \le a_{k+1}, k=0,…,n−1k = 0, \dots, n-1, to write
∑k=1n−1akak+1=∑k=1n−1Ak−Ak−1ak+1=∑k=1n−2Ak(1ak+1−1ak+2)+An−1an≤∑k=1n−2ak+1(1ak+1−1ak+2)+1=∑k=1n−2(1−ak+1ak+2)+1=n−1+a1a2−∑k=1n−1akak+1≤n−∑k=1n−1akak+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=1n−1ak/ak+1≤n/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,…,n−1k = 1, \dots, n-1, which is clearly the case if and only if ak=2k−2a1a_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 n≥2n \ge 2 that sn(a1,…,an)=a1/a2+a2/a3+⋯+an−1/an≤n/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 ak≥a1+⋯+ak−1a_k \ge a_1 + \dots + a_{k-1}, k=2,…,nk = 2, \dots, n, and equality holds if and only if ak=2k−2a1a_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<a1≤a20 < 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<a1≤a20 < a_1 \le a_2 and a1+a2≤a3a_1 + a_2 \le a_3; in both cases, equality holds if and only if the aka_k are as stated.
Now let n≥4n \ge 4, let a1,…,ana_1, \dots, a_n be positive real numbers such that ak≥a1+⋯+ak−1a_k \ge a_1 + \dots + a_{k-1}, k=2,…,nk = 2, \dots, n, and write
sn(a1,…,an)≤sn(a1,…,an−1,a1+⋯+an−1)=sn−2(a1,…,an−2)+an−2an−1+an−1a1+⋯+an−1. \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
an−2an−1+an−1a1+⋯+an−1≤an−2a1+⋯+an−2+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)≤sn−1(a1,…,an−2,a1+⋯+an−2)+1/2≤(n−1)/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 an−1−a1−⋯−an−2≥0a_{n-1} - a_1 - \dots - a_{n-2} \ge 0 and an−1(an−2−a1−⋯−an−3)+2an−2(a1+⋯+an−2)≥2an−2(a1+⋯+an−2)>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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.