Maths Olympiad Prep

Library / /100 of 106

Algebra Difficulty 9.0 IMO level Prove it IMO

Let a1,a2,,an,ka_{1}, a_{2}, \ldots, a_{n}, k, and MM be positive integers such that
1a1+1a2++1an=k and a1a2an=M. \frac{1}{a_{1}}+\frac{1}{a_{2}}+\cdots+\frac{1}{a_{n}}=k \quad \text{ and } \quad a_{1} a_{2} \ldots a_{n}=M .
If M>1M>1, prove that the polynomial
P(x)=M(x+1)k(x+a1)(x+a2)(x+an) P(x)=M(x+1)^{k}-\left(x+a_{1}\right)\left(x+a_{2}\right) \cdots\left(x+a_{n}\right)
has no positive roots.

Solutions — 2

Solution 1

We first prove that, for x>0x>0,
ai(x+1)1/aix+ai, \begin{equation*} a_{i}(x+1)^{1 / a_{i}} \leqslant x+a_{i}, \tag{1} \end{equation*}
with equality if and only if ai=1a_{i}=1. It is clear that equality occurs if ai=1a_{i}=1.
If ai>1a_{i}>1, the AM-GM inequality applied to a single copy of x+1x+1 and ai1a_{i}-1 copies of 1 yields
(x+1)+1+1++1ai1 ones ai(x+1)1ai1aiai(x+1)1/aix+ai. \frac{(x+1)+\overbrace{1+1+\cdots+1}^{a_{i}-1 \text{ ones }}}{a_{i}} \geqslant \sqrt[a_{i}]{(x+1) \cdot 1^{a_{i}-1}} \Longrightarrow a_{i}(x+1)^{1 / a_{i}} \leqslant x+a_{i} .
Since x+1>1x+1>1, the inequality is strict for ai>1a_{i}>1.
Multiplying the inequalities (1) for i=1,2,,ni=1,2, \ldots, n yields
i=1nai(x+1)1/aii=1n(x+ai)M(x+1)i=1n1/aii=1n(x+ai)0P(x)0 \prod_{i=1}^{n} a_{i}(x+1)^{1 / a_{i}} \leqslant \prod_{i=1}^{n}\left(x+a_{i}\right) \Longleftrightarrow M(x+1)^{\sum_{i=1}^{n} 1 / a_{i}}-\prod_{i=1}^{n}\left(x+a_{i}\right) \leqslant 0 \Longleftrightarrow P(x) \leqslant 0
with equality iff ai=1a_{i}=1 for all i{1,2,,n}i \in\{1,2, \ldots, n\}. But this implies M=1M=1, which is not possible. Hence P(x)<0P(x)<0 for all xR+x \in \mathbb{R}^{+}, and PP has no positive roots.

Solution 2

We will prove that, in fact, all coefficients of the polynomial P(x)P(x) are non-positive, and at least one of them is negative, which implies that P(x)<0P(x)<0 for x>0x>0.
Indeed, since aj1a_{j} \geqslant 1 for all jj and aj>1a_{j}>1 for some jj (since a1a2an=M>1a_{1} a_{2} \ldots a_{n}=M>1 ), we have k=1a1+1a2++1an<nk=\frac{1}{a_{1}}+\frac{1}{a_{2}}+\cdots+\frac{1}{a_{n}}<n, so the coefficient of xnx^{n} in P(x)P(x) is 1<0-1<0. Moreover, the coefficient of xrx^{r} in P(x)P(x) is negative for k<rn=deg(P)k<r \leqslant n=\operatorname{deg}(P).
For 0rk0 \leqslant r \leqslant k, the coefficient of xrx^{r} in P(x)P(x) is
M(kr)1i1<i2<<inrnai1ai2ainr=a1a2an(kr)1i1<i2<<inrnai1ai2ainr, M \cdot\binom{k}{r}-\sum_{1 \leqslant i_{1}<i_{2}<\cdots<i_{n-r} \leqslant n} a_{i_{1}} a_{i_{2}} \cdots a_{i_{n-r}}=a_{1} a_{2} \cdots a_{n} \cdot\binom{k}{r}-\sum_{1 \leqslant i_{1}<i_{2}<\cdots<i_{n-r} \leqslant n} a_{i_{1}} a_{i_{2}} \cdots a_{i_{n-r}},
which is non-positive iff
(kr)1j1<j2<<jrn1aj1aj2ajr. \begin{equation*} \binom{k}{r} \leqslant \sum_{1 \leqslant j_{1}<j_{2}<\cdots<j_{r} \leqslant n} \frac{1}{a_{j_{1}} a_{j_{2}} \cdots a_{j_{r}}} . \tag{2} \end{equation*}
We will prove (2) by induction on rr. For r=0r=0 it is an equality because the constant term of P(x)P(x) is P(0)=0P(0)=0, and if r=1r=1, (2) becomes k=i=1n1aik=\sum_{i=1}^{n} \frac{1}{a_{i}}. For r>1r>1, if (2) is true for a given r<kr<k, we have
(kr+1)=krr+1(kr)krr+1.1j1<j2<<jrn1aj1aj2ajr, \binom{k}{r+1}=\frac{k-r}{r+1} \cdot\binom{k}{r} \leqslant \frac{k-r}{r+1} . \sum_{1 \leqslant j_{1}<j_{2}<\cdots<j_{r} \leqslant n} \frac{1}{a_{j_{1}} a_{j_{2}} \cdots a_{j_{r}}},
and it suffices to prove that
krr+1.1j1<j2<<jrn1aj1aj2ajr1j1<<jr<jr+1n1aj1aj2ajrajr+1, \frac{k-r}{r+1} . \sum_{1 \leqslant j_{1}<j_{2}<\cdots<j_{r} \leqslant n} \frac{1}{a_{j_{1}} a_{j_{2}} \cdots a_{j_{r}}} \leqslant \sum_{1 \leqslant j_{1}<\cdots<j_{r}<j_{r+1} \leqslant n} \frac{1}{a_{j_{1}} a_{j_{2}} \cdots a_{j_{r}} a_{j_{r+1}}},
which is equivalent to
(1a1+1a2++1anr)1j1<j2<<jrn1aj1aj2ajr(r+1)1j1<<jr<jr+1n1aj1aj2ajrajr+1. \left(\frac{1}{a_{1}}+\frac{1}{a_{2}}+\cdots+\frac{1}{a_{n}}-r\right) \sum_{1 \leqslant j_{1}<j_{2}<\cdots<j_{r} \leqslant n} \frac{1}{a_{j_{1}} a_{j_{2}} \cdots a_{j_{r}}} \leqslant(r+1) \sum_{1 \leqslant j_{1}<\cdots<j_{r}<j_{r+1} \leqslant n} \frac{1}{a_{j_{1}} a_{j_{2}} \cdots a_{j_{r}} a_{j_{r+1}}} .
Since there are r+1r+1 ways to choose a fraction 1aji\frac{1}{a_{j_{i}}} from 1aj1aj2ajrajr+1\frac{1}{a_{j_{1}} a_{j_{2}} \cdots a_{j_{r}} a_{j_{r+1}}} to factor out, every term 1aj1aj2ajrajr+1\frac{1}{a_{j_{1}} a_{j_{2}} \cdots a_{j_{r}} a_{j_{r+1}}} in the right hand side appears exactly r+1r+1 times in the product
(1a1+1a2++1an)1j1<j2<<jrn1aj1aj2ajr. \left(\frac{1}{a_{1}}+\frac{1}{a_{2}}+\cdots+\frac{1}{a_{n}}\right) \sum_{1 \leqslant j_{1}<j_{2}<\cdots<j_{r} \leqslant n} \frac{1}{a_{j_{1}} a_{j_{2}} \cdots a_{j_{r}}} .
Hence all terms in the right hand side cancel out.

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.