Maths Olympiad Prep

Library / /290 of 299

Algebra Difficulty 7.7 National Olympiad, round 2 Prove it Iran

Let x1<x2<<xnx_1 < x_2 < \dots < x_n be real numbers. Define the function f:RRf : \mathbb{R} \rightarrow \mathbb{R}
f(x)=(xx2)(xx3)(xxn)(x1x2)(x1x3)(x1xn)++(xx1)(xx2)(xxn1)(xnx1)(xnx2)(xnxn1) f(x) = \left| \frac{(x-x_2)(x-x_3)\cdots(x-x_n)}{(x_1-x_2)(x_1-x_3)\cdots(x_1-x_n)} \right| + \cdots + \left| \frac{(x-x_1)(x-x_2)\cdots(x-x_{n-1})}{(x_n-x_1)(x_n-x_2)\cdots(x_n-x_{n-1})} \right|
Prove that there exists an i{1,,n1}i \in \{1, \dots, n-1\} such that for all x(xi,xi+1)x \in (x_i, x_{i+1}), we have f(x)<nf(x) < \sqrt{n}.

Solution

If for some ii, xi=xi+1x_i = x_{i+1} then we have nothing to do. Assume now, that xixi+1x_i \neq x_{i+1}, 0in+10 \le i \le n+1. Consider the polynomial P(x)=Q1(x)2++Qn(x)21P(x) = Q_1(x)^2 + \dots + Q_n(x)^2 - 1. It at most has 2(n1)2(n-1) roots and it is easy to verify that x1,,xnx_1, \dots, x_n are roots. Hence, there is ii, 1in11 \le i \le n-1 such that P(x)<0P(x) < 0 for all x(xi,xi+1)x \in (x_i, x_{i+1}). On the other hand, according to Cauchy-Schwartz inequality,
(k=1nQk(x))2n(Q1(x)2++Qn(x)2)<n. \left( \sum_{k=1}^{n} |Q_k(x)| \right)^2 \le n(Q_1(x)^2 + \dots + Q_n(x)^2) < n.
We are done.

Proof Details.

First, note that using Cauchy's inequality, it is sufficient to show that:
((xx2)(xx3)(xxn)(x1x2)(x1x3)(x1xn))2++((xx2)(xx3)(xxn)(x1x2)(x1x3)(x1xn))21 \left( \frac{(x-x_2)(x-x_3)\dots(x-x_n)}{(x_1-x_2)(x_1-x_3)\dots(x_1-x_n)} \right)^2 + \dots + \left( \frac{(x-x_2)(x-x_3)\dots(x-x_n)}{(x_1-x_2)(x_1-x_3)\dots(x_1-x_n)} \right)^2 \le 1
Let's denote this function by h(x)h(x) and define g(x)=h(x)1g(x) = h(x) - 1. This is a polynomial of degree 2n22n-2 with positive coefficients, and x1,x2,x_1, x_2, \dots are its roots. If this polynomial is decreasing at xnx_n and increasing at xi+1x_{i+1}, then, there are at least two roots in this interval because the function is negative at the beginning of the interval and at the end of the interval, the function is also negative. By contradiction, if it becomes positive somewhere, by Intermediate Value Theorem (IVT) it must have at least two roots in this interval.
If the function is increasing or decreasing at both ends of an interval, it must have at least one root of this interval. For example, if it is increasing, then the sign of function near xix_i is positive and near xi+1x_{i+1} is negative, and by intermediate value theorem it should have a root. According to the following claim, the function is decreasing at x1x_1 and increasing at xnx_n. Therefore, if we group the points based on whether the function is increasing or decreasing, the number of increasing blocks and decreasing blocks are equal.
The function has one root in any interval where its ends are within a block, and two roots in any interval where its beginning is in a decreasing block and its end is in an increasing block. Therefore, we have at least n1n-1 roots inside intervals together with x1,x2,,xnx_1, x_2, \dots, x_n. We get 2n12n-1 roots for a polynomial of degree 2n22n-2, contradiction.

Lemma.

The function hh is decreasing before x1x_1 and increasing after xnx_n.

Proof.

First, note that:
(xx2)(xx3)(xxn)(x1x2)(x1x3)(x1xn) \frac{(x-x_2)(x-x_3)\dots(x-x_n)}{(x_1-x_2)(x_1-x_3)\dots(x_1-x_n)}
is a polynomial of degree n1n-1 with n2n-2 roots. Its derivative therefore has one root in each interval (xi,xi+1)(x_i, x_{i+1}). Since the derivative cannot have any other roots due to its degree, the polynomial itself is monotonic before x1x_1 and after xnx_n. Therefore,
hh is also monotone. Since hh is an even degree polynomial with a positive leading coefficient, in the first interval, it is decreasing, and in the second interval, it must be increasing. ■

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.