Maths Olympiad Prep

Library / /118 of 121

Algebra Difficulty 7.5 National Olympiad, round 2 Prove it India

Suppose a0,,a100a_0, \dots, a_{100} are positive reals. Consider the following polynomial for each kk in {0,1,,100}\{0, 1, \dots, 100\}:
a100+kx100+100a99+kx99+a98+kx98+a97+kx97++a2+kx2+a1+kx+ak, a_{100+k}x^{100} + 100a_{99+k}x^{99} + a_{98+k}x^{98} + a_{97+k}x^{97} + \dots + a_{2+k}x^2 + a_{1+k}x + a_k,
where indices are taken modulo 101, i.e., a100+i=ai1a_{100+i} = a_{i-1} for any ii in {1,2,,100}\{1, 2, \dots, 100\}. Show that it is impossible that each of these 101 polynomials has all its roots real.

Solution

Suppose for contradiction that all 101 polynomials have all real roots. Let Pk(x)P_k(x) denote the kk-th polynomial:
Pk(x)=a100+kx100+100a99+kx99+a98+kx98+a97+kx97++a2+kx2+a1+kx+ak, P_k(x) = a_{100+k}x^{100} + 100a_{99+k}x^{99} + a_{98+k}x^{98} + a_{97+k}x^{97} + \dots + a_{2+k}x^2 + a_{1+k}x + a_k,
where all indices are modulo 101.

Note that all coefficients aia_i are positive reals.

Let SS be the 101×101101 \times 101 matrix whose kk-th row (for k=0,1,,100k = 0, 1, \dots, 100) is the vector of coefficients of Pk(x)P_k(x), i.e.,
(a100+k, 100a99+k, a98+k, a97+k, , a2+k, a1+k, ak) (a_{100+k},\ 100a_{99+k},\ a_{98+k},\ a_{97+k},\ \dots,\ a_{2+k},\ a_{1+k},\ a_k)
with indices modulo 101.

Let us consider the sum of all these polynomials:
k=0100Pk(x)=k=0100(a100+kx100+100a99+kx99+a98+kx98++a1+kx+ak) \sum_{k=0}^{100} P_k(x) = \sum_{k=0}^{100} \left( a_{100+k}x^{100} + 100a_{99+k}x^{99} + a_{98+k}x^{98} + \dots + a_{1+k}x + a_k \right)
Let us compute the coefficient of xmx^m in this sum for m=0,1,,100m = 0, 1, \dots, 100.

- For m=100m = 100, the coefficient is k=0100a100+k=k=0100ak\sum_{k=0}^{100} a_{100+k} = \sum_{k=0}^{100} a_k (since 100+k100+k runs over all residues mod 101 as kk runs from 0 to 100).
- For m=99m = 99, the coefficient is k=0100100a99+k=100k=0100ak\sum_{k=0}^{100} 100a_{99+k} = 100 \sum_{k=0}^{100} a_k.
- For m=98m = 98, the coefficient is k=0100a98+k=k=0100ak\sum_{k=0}^{100} a_{98+k} = \sum_{k=0}^{100} a_k.
- For m=97m = 97, the coefficient is k=0100a97+k=k=0100ak\sum_{k=0}^{100} a_{97+k} = \sum_{k=0}^{100} a_k.
- ...
- For m=1m = 1, the coefficient is k=0100a1+k=k=0100ak\sum_{k=0}^{100} a_{1+k} = \sum_{k=0}^{100} a_k.
- For m=0m = 0, the coefficient is k=0100ak\sum_{k=0}^{100} a_k.

So, the sum is:
k=0100Pk(x)=(k=0100ak)x100+100(k=0100ak)x99+(k=0100ak)x98++(k=0100ak)x0 \sum_{k=0}^{100} P_k(x) = (\sum_{k=0}^{100} a_k) x^{100} + 100(\sum_{k=0}^{100} a_k) x^{99} + (\sum_{k=0}^{100} a_k) x^{98} + \dots + (\sum_{k=0}^{100} a_k) x^0
That is,
k=0100Pk(x)=(k=0100ak)(x100+100x99+x98+x97++x2+x+1) \sum_{k=0}^{100} P_k(x) = (\sum_{k=0}^{100} a_k) \left( x^{100} + 100x^{99} + x^{98} + x^{97} + \dots + x^2 + x + 1 \right)

Now, k=0100ak>0\sum_{k=0}^{100} a_k > 0 since all ak>0a_k > 0.

Therefore, the sum of all 101 polynomials is a positive constant times the polynomial
Q(x)=x100+100x99+x98+x97++x2+x+1 Q(x) = x^{100} + 100x^{99} + x^{98} + x^{97} + \dots + x^2 + x + 1

But Q(x)Q(x) is a degree 100 polynomial with real coefficients. Let us check whether Q(x)Q(x) can have all real roots.

Suppose Q(x)Q(x) has all real roots. But the coefficient of x99x^{99} is 100100, which is much larger than the other coefficients (which are all 11). For a real-rooted degree 100 polynomial with all positive coefficients, the sequence of coefficients must be log-concave (by Newton's inequalities). That is, for all ii, ai2ai1ai+1a_i^2 \geq a_{i-1} a_{i+1}.

But for x99x^{99}, the coefficient is 100100, and for x100x^{100} and x98x^{98}, the coefficients are 11 each. So,
1002=10,00011=1 100^2 = 10,000 \geq 1 \cdot 1 = 1
which is true, but let's check the log-concavity at x99x^{99}:
100211 100^2 \geq 1 \cdot 1
which is true, but let's check at x98x^{98}:
121001    1100 1^2 \geq 100 \cdot 1 \implies 1 \geq 100
which is false.

Therefore, the sequence of coefficients is not log-concave, so Q(x)Q(x) cannot have all real roots.

But Q(x)Q(x) is a sum of polynomials, each of which (by assumption) has all real roots. The sum of real-rooted polynomials with positive coefficients is also real-rooted only if the sequence of coefficients is log-concave. Since Q(x)Q(x) is not real-rooted, at least one of the Pk(x)P_k(x) cannot be real-rooted.

Therefore, it is impossible that all 101 polynomials have all roots real.

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.