Maths Olympiad Prep

Library / /29 of 65

Algebra Difficulty 5.7 AIME, harder Prove it Romania

Let nn be a positive integer and x1,x2,,xn>0x_1, x_2, \dots, x_n > 0 be real numbers so that
x1+x2++xn=1x12+1x22++1xn2. x_1 + x_2 + \dots + x_n = \frac{1}{x_1^2} + \frac{1}{x_2^2} + \dots + \frac{1}{x_n^2}.

Show that for each positive integer knk \le n, there are kk numbers among x1,x2,,xnx_1, x_2, \dots, x_n whose sum is at least kk.

Solution

Arguing by contradiction, suppose that every sum of kk numbers from x1,x2,,xnx_1, x_2, \dots, x_n is strictly less than kk. Then the numbers
aj=xj+xj+1++xj+k1,j=1,2,,n a_j = x_j + x_{j+1} + \dots + x_{j+k-1}, \quad j = 1, 2, \dots, n
are also less than kk (where the indices from the sums aja_j are considered to be taken modulo nn).
Adding up yields a1+a2++an<nka_1 + a_2 + \dots + a_n < nk and, since
a1+a2++an=k(x1+x2++xn), a_1 + a_2 + \dots + a_n = k(x_1 + x_2 + \dots + x_n),
we get
x1+x2++xn<n. x_1 + x_2 + \dots + x_n < n.

But n2(k=1nxk)(k=1n1xk)<nk=1n1xkn^2 \le \left(\sum_{k=1}^n x_k\right) \left(\sum_{k=1}^n \frac{1}{x_k}\right) < n \sum_{k=1}^n \frac{1}{x_k}, so k=1n1xk>n\sum_{k=1}^n \frac{1}{x_k} > n. It follows that
k=1nxk=k=1n1xk21n(k=1n1xk)2>1nn2=n, \sum_{k=1}^{n} x_k = \sum_{k=1}^{n} \frac{1}{x_k^2} \ge \frac{1}{n} \left( \sum_{k=1}^{n} \frac{1}{x_k} \right)^2 > \frac{1}{n} \cdot n^2 = n,
contradiction.

Alternative Solution:
Suppose that x1x2xnx_1 \le x_2 \le \dots \le x_n; it is enough to prove that
xnk+1++xn1+xnk, for each k=1,2,,n. x_{n-k+1} + \dots + x_{n-1} + x_n \ge k, \text{ for each } k=1, 2, \dots, n.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.