Maths Olympiad Prep

Library / /3 of 54

Algebra Difficulty 5.0 AIME Prove it China

Let nn be an integer, n≥2n \ge 2, and x1,x2,…,xn∈[0,1]x_1, x_2, \dots, x_n \in [0, 1]. Prove that
∑1≤k<l≤nkxkxl≤n−13∑k=1nkxk. \sum_{1 \le k < l \le n} kx_k x_l \le \frac{n-1}{3} \sum_{k=1}^{n} kx_k.

Solution

As x1,x2,…,xn∈[0,1]x_1, x_2, \dots, x_n \in [0, 1], xixj≤xix_i x_j \le x_i, so we have
3∑1≤k<l≤nkxkxl=∑1≤k<l≤n3kxkxl≤∑1≤k<l≤n(kxk+2kxl). 3 \sum_{1 \le k < l \le n} kx_k x_l = \sum_{1 \le k < l \le n} 3k x_k x_l \le \sum_{1 \le k < l \le n} (k x_k + 2k x_l).
For 1≤k≤n1 \le k \le n, the coefficient of xkx_k in the last sum is
2[1+2+⋯+(k−1)]+k(n−k)=k(n−1), 2[1 + 2 + \dots + (k-1)] + k(n-k) = k(n-1),
so we have
3∑1≤k<l≤nkxkxl≤∑1≤k<l≤n(kxk+2kxl)=∑k=1nk(n−1)xk=(n−1)∑k=1nkxk, \begin{aligned} 3 \sum_{1 \le k < l \le n} kx_k x_l &\le \sum_{1 \le k < l \le n} (k x_k + 2k x_l) = \sum_{k=1}^{n} k(n-1)x_k \\ &= (n-1) \sum_{k=1}^{n} kx_k, \end{aligned}
and hence the desired inequality holds. □\square

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.