Maths Olympiad Prep

Library / /16 of 48

Algebra Difficulty 6.0 National Olympiad Prove it Turkey

At least dd coefficients of a polynomial P(x)P(x) of degree dd with real coefficients are equal to 11. Find the maximal value of dd if P(x)P(x) has dd real roots.

*Note: Roots of P(x)P(x) need not be distinct.*

Solutions — 2

Solution 1

The polynomial x4+x34x2+x+1=(x1)2(x2+3x+1)x^4 + x^3 - 4x^2 + x + 1 = (x-1)^2(x^2 + 3x + 1) satisfies the conditions. Let us show that for d5d \ge 5 there is no polynomial satisfying given conditions.

Solution 1. Let x1,x2,,xdx_1, x_2, \dots, x_d be the roots, SkS_k be the sum of all kk-tuple products of roots. Using Vieta theorem, we get
S122S2=i=1dxi20. S_1^2 - 2S_2 = \sum_{i=1}^{d} x_i^2 \geq 0.
When the first three coefficients are 11, we have S1=1,S2=1S_1 = -1, S_2 = 1 and S122S2=1<0S_1^2 - 2S_2 = -1 < 0, which is a contradiction. Hence at least one of the first three coefficients should not be equal to 11. This means that all roots are non-zero and hence we obtain:
(Sd1Sd)22(Sd2Sd)=i=1d1xi2>0. \left(\frac{S_{d-1}}{S_d}\right)^2 - 2\left(\frac{S_{d-2}}{S_d}\right) = \sum_{i=1}^{d} \frac{1}{x_i^2} > 0.
If the last three coefficients are 11, we get Sd2=Sd1=SdS_{d-2} = -S_{d-1} = S_d and hence we conclude that (Sd1Sd)2<2(Sd2Sd)\left(\frac{S_{d-1}}{S_d}\right)^2 < 2\left(\frac{S_{d-2}}{S_d}\right), which is again a contradiction.
For d5d \ge 5 case, as dd coefficients out of d+1d+1 coefficients are 11, we conclude that either the first three or the last three coefficients should be 11. Hence, we are done.

Solution 2

The polynomial x4+x34x2+x+1=(x1)2(x2+3x+1)x^4 + x^3 - 4x^2 + x + 1 = (x-1)^2(x^2 + 3x + 1) satisfies the conditions. Let us show that for d5d \ge 5 there is no polynomial satisfying given conditions.

Solution 2. We will find a contradiction for d5d \ge 5 case. We can express the polynomial as P(x)=xd+xd1++1+axbP(x) = x^d + x^{d-1} + \dots + 1 + a x^b where bb is an integer satisfying 0bd0 \le b \le d and aa is a real number. Since all roots of P(x)P(x) are real numbers, all roots of the polynomial Q(x)=(x1)P(x)=xd+11+axb+1axbQ(x) = (x-1)P(x) = x^{d+1} - 1 + a x^{b+1} - a x^b should be real numbers, too. If zero is a root of Q(x)Q(x), then we get a=1,b=0a = -1, b = 0 and in this case all roots of Q(x)=xd+1xQ(x) = x^{d+1} - x cannot be real. So, all roots of Q(x)Q(x) should be non-zero.
The polynomial Q(x)Q(x) has at most 44 non-zero coefficients. By Descartes' rule of signs, QQ has at most 33 positive real roots. Q(x)=(1)d+1xd+11+a(1)b+1(xb+1+xb)Q(-x) = (-1)^{d+1} x^{d+1} - 1 + a(-1)^{b+1}(x^{b+1} + x^b) has also at most 44 non-zero coefficients. If there are exactly 44 non-zero coefficients, the coefficients of xb+1x^{b+1} and xbx^b should have the same sign. (Otherwise we would have at most 33 non-zero coefficients.) Therefore, in both cases, using Descartes' rule of signs again, we conclude that Q(x)Q(-x) has at most 22 positive real roots. As zero is not a root, Q(x)Q(x) can have at most 55 real roots. The degree of Q(x)Q(x) is d+16d+1 \ge 6 and hence all roots cannot be real. This finishes the proof.

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.