Maths Olympiad Prep

Library / /372 of 520

Algebra Difficulty 5.6 AIME, harder Find the answer

6. Given that n,kn, k are positive integers, n>kn>k. Given real numbers a1,a2,,an(k1,k)a_{1}, a_{2}, \cdots, a_{n} \in(k-1, k). Let positive real numbers x1,x2x_{1}, x_{2}, ,xn\cdots, x_{n} satisfy that for any kk-element subset II of {1,2,,n}\{1,2, \cdots, n\}, we have iIxiiIai\sum_{i \in I} x_{i} \leqslant \sum_{i \in I} a_{i}. Find the maximum value of x1x2xnx_{1} x_{2} \cdots x_{n}.
(Zhai Zhenhua, problem contributor)

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

6. The maximum value is a1a2ana_{1} a_{2} \cdots a_{n}.

If xi=ai(1in)x_{i}=a_{i}(1 \leqslant i \leqslant n), then x1,x2,,xnx_{1}, x_{2}, \cdots, x_{n} satisfy the conditions, and x1x2xn=a1a2anx_{1} x_{2} \cdots x_{n}=a_{1} a_{2} \cdots a_{n}.
Next, we prove: x1x2xna1a2anx_{1} x_{2} \cdots x_{n} \leqslant a_{1} a_{2} \cdots a_{n}.
When k=1k=1, the conclusion is obvious. By the condition, we have xiai(1in)x_{i} \leqslant a_{i}(1 \leqslant i \leqslant n).
Assume k2k \geqslant 2.
Without loss of generality, let
a1x1a2x2anxn a_{1}-x_{1} \leqslant a_{2}-x_{2} \leqslant \cdots \leqslant a_{n}-x_{n} \text {. }

If a1x10a_{1}-x_{1} \geqslant 0, then aixi(1in)a_{i} \geqslant x_{i}(1 \leqslant i \leqslant n), and the conclusion is obviously true.
Assume a1x1<0a_{1}-x_{1} < 0, \\
$0 d s+1 d k d n .\text{d s+1 d k d n .}

From equation (1), we know
i=1sdi+i=s+1kdi0i=s+1kdii=1sdi. -\sum_{i=1}^{s} d_{i}+\sum_{i=s+1}^{k} d_{i} \geqslant 0 \Rightarrow \sum_{i=s+1}^{k} d_{i} \geqslant \sum_{i=1}^{s} d_{i} .

Let M=i=1sdi,N=i=s+1ndiM=\sum_{i=1}^{s} d_{i}, N=\sum_{i=s+1}^{n} d_{i}. Then
Nns=i=s+1ndinsi=s+1kdiksMks \frac{N}{n-s}=\frac{\sum_{i=s+1}^{n} d_{i}}{n-s} \geqslant \frac{\sum_{i=s+1}^{k} d_{i}}{k-s} \geqslant \frac{M}{k-s} \text {. }

Notice that, for j>sj>s, we have dj<aj<kd_{j}<a_{j}<k.
Using the AM-GM inequality, we get
i=1nxiai=(i=1s(1+diai))(j=s+1n(1djaj))(i=1s(1+dik1))(j=s+1n(1djk))(1n(i=1s(1+dik1)+i=s+1n(1dik)))n=(1+Mn(k1)Nnk)n(1+Mn(k1)(ns)Mnk(ks))n(1+Mn(k1)(k+1s)Mnk(ks))n=(1+Mnk(kk1ks+1ks))n1. \begin{array}{l} \prod_{i=1}^{n} \frac{x_{i}}{a_{i}}=\left(\prod_{i=1}^{s}\left(1+\frac{d_{i}}{a_{i}}\right)\right)\left(\prod_{j=s+1}^{n}\left(1-\frac{d_{j}}{a_{j}}\right)\right) \\ \leqslant\left(\prod_{i=1}^{s}\left(1+\frac{d_{i}}{k-1}\right)\right)\left(\prod_{j=s+1}^{n}\left(1-\frac{d_{j}}{k}\right)\right) \\ \leqslant\left(\frac{1}{n}\left(\sum_{i=1}^{s}\left(1+\frac{d_{i}}{k-1}\right)+\sum_{i=s+1}^{n}\left(1-\frac{d_{i}}{k}\right)\right)\right)^{n} \\ =\left(1+\frac{M}{n(k-1)}-\frac{N}{n k}\right)^{n} \\ \leqslant\left(1+\frac{M}{n(k-1)}-\frac{(n-s) M}{n k(k-s)}\right)^{n} \\ \leqslant\left(1+\frac{M}{n(k-1)}-\frac{(k+1-s) M}{n k(k-s)}\right)^{n} \\ =\left(1+\frac{M}{n k}\left(\frac{k}{k-1}-\frac{k-s+1}{k-s}\right)\right)^{n} \\ \leqslant 1 . \end{array}

Thus, the conclusion is proved.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.