Bob writes polynomials

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Bob writes polynomials

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: India EGMO 2022 TST P6

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

222 posts

#1 h Nov 28, 2021, 11:39 AM • 3 Y

Y by GuvercinciHoca, Anshul_singh, Rounak_iitr

Suppose $P(x)$ is a non-constant polynomial with real coefficients, and even degree. Bob writes the polynomial $P(x)$ on a board. At every step, if the polynomial on the board is $f(x)$ , he can replace it with

1. $f(x)+c$ for a real number $c$ , or
2. the polynomial $P(f(x))$ .

Can he always find a finite sequence of steps so the final polynomial on the board has exactly $2020$ real roots? What about $2021$ ?

~Sutanay Bhattacharya

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

222 posts

#2 h Nov 28, 2021, 11:43 AM • 1 Y

Y by Anshul_singh

The answer is yes for $2020$ . In fact, we prove that for any positive even number $k$ , Bob can make end up with a polynomial with exactly $k$ real roots.

The argument is similar for negative leading coefficient.

Let us first prove a lemma:
Lemma If $f(x)$ is a non-constant polynomial with even degree and positive leading coefficient, and $N$ is a positive real, one can find $C>0$ so that the following holds: for all $c>C$ , the equation $f(x)=c$ has exactly two roots, and the difference between those roots is at least $N$ .

Proof
Suppose $f(x)=a_nx^n+\cdots +a_0$ for $n$ even. We choose a large $x_0$ and take $C_1=a_nx_0^n+|a_{n-1}|x_0^{n-1}+\cdots+|a_1|x_0+|a_0|\ge f(x_0)$ . Now for $c>C_1$ , $f(x)=c$ has at least one positive root, since $f(0)<f(x_0)<c$ (this can be ensured for large enough $x_0$ ) and $f(x)\to \infty$ as $x\to \infty$ . Also, any such root must be at least $x_0$ ; indeed, if $0\le x_1<x_0$ , then
$f(x_1)\le a_nx_1^n+|a_{n-1}|x_1^{n-1}+\cdots+|a_0|\\ \le a_nx_0^n+|a_{n-1}|x_0^{n-1}+\cdots+|a_1|x_0+|a_0|\le C_1<c$ so $x_1$ cannot be a root. Now if there are two positive roots $x_1>x_2$ , then $x_1,x_2\ge x_0$ . So now $0=f(x_1)-f(x_2)=(x_1-x_2)\left(a_n\frac{x_1^n-x_2^n}{x_1-x_2}+\cdots +a_1\frac{x_1-x_2}{x_1-x_2}\right)$ Notice that $jx_2^{j-1}<\frac{x_1^j-x_2^j}{x_1-x_2}<jx_1^{j-1}, \frac{x_1^n-x_2^n}{x_1-x_2}>x_1^{n-1}.$ Thus the second factor can be bounded as $\left(a_n\frac{x_1^n-x_2^n}{x_1-x_2}+\cdots +a_1\frac{x_1-x_2}{x_1-x_2}\right)> a_nx_1^n-|a_{n-1}|(n-1)x_1^{n-2}-\cdots -|a_1|.$ The last expression is a polynomial in $x_1$ with positive leading coefficient, so if $x_0$ is large enough, this will be positive for $x_1>x_0$ . This means cannot hold. Thus there is exactly one positive root, and it is at least $x_0$ .

Using the same argument on $f(-x)$ one can find $-x_0'$ and $C_2$ so that $f(x)=c$ has exactly one negative root, which is smaller than $-x_0'$ . Taking $C=\max\{C_1,C_2\}$ now gives us the required $C$ . $\square$

For the main problem, first suppose $P$ has positive leading coefficient. By the lemma, we can find $c$ so that $P(x)-c$ has exactly $2$ real roots, so the base case $k=2$ is true. Now suppose Bob has constructed a polynomial $f$ with $k$ real roots. Clearly this has even degree and positive leading coefficient, so suppose $C_f$ is a number so that $f(x)-c$ has exactly two roots for all $c>C_f$ . By the lemma, we can find $c$ so that $P(x)=c$ has exactly two roots, $a_1$ and $a_2$ and $a_1-a_2>C_f$ . Now let Bob modify $f(x)$ into $P(f(x)+a_2)-c$ . If $x$ is a root of this, then either $f(x)+a_2=a_2$ , which gives $k$ values for $x$ , or $f(x)+a_2=a_1\implies f(x)=a_1-a_2$ , which has exactly two roots by assumption. This gives exactly $k+2$ roots, as desired.

For $2021$ , we claim that Bob cannot always succeed. Indeed, let $P(x)=x^2(x^2-1^2)(x^2-2^2)\cdots (x^2-1011^2).$ Note that $P(x)=P(-x)$ for all $x$ , and it has $2023$ roots, including $0$ . Suppose after a finite sequence of moves, the polynomial on the board is $f(P(x))$ and this has exactly $2021$ real roots. Since $x$ is a root of this if and only if $-x$ is, for this to have odd number of roots, $x=0$ needs to be a root. Thus $f(P(0))=f(0)=0.$ But then each of the $2023$ roots of $P$ is a root, contradiction. $\square$

This post has been edited 3 times. Last edited by Rg230403, Nov 28, 2021, 1:28 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1184 posts

L567

#3 h Aug 19, 2022, 6:18 AM

Y by

My solution for $2021$ is essentially the same as the above solution, so I'll only post $2020$ because I think this is a more motivated version.

Its reasonable to guess that all evens are achievable since $2$ for sure is and the question is asked in this way, so its natural to want to induct from $n \rightarrow n+2$ . Suppose at some point we had a polynomial $g(x)$ on the board with exactly $n$ real roots, suppose we add a constant $c_1$ , apply $P$ on this, and add $c_2$ , then we want $P(g(x)+c_1) = -c_2$ . Suppose $P(x) = -c_2$ has roots $\alpha_1, \alpha_2, \cdots, \alpha_k$ , since these are too many to deal with, we want to keep $k$ as small as possible. If $k = 1$ , then there can be at most $n$ roots for this new polynomial too, so that's no use, so maybe we want $k = 2$ , so suppose these two roots are $\alpha$ and $\beta$ . Then one set of roots we get of this polynomial are when $g(x) + c_1 = \alpha$ and when $g(x) + c_1 = \beta$ . Because we want to use that $g$ has exactly $n$ roots, we can set $c_1 = \alpha$ , so that part has $n$ roots. So for the induction to work out, we want $g(x) = \beta - \alpha$ to have exactly two roots.

But $g$ is a polynomial of even degree, so if we take this value $\beta - \alpha$ to be sufficiently large (in magnitude, sign depending on the sign of the leading coefficient), then there's going to be only two real roots, but $\beta$ and $\alpha$ are roots of $P(x) = -c_2$ , so we need to choose $c_2$ such that $P + c_2$ has two roots which are sufficiently far apart. This will also take care of the base case of the induction.

So to prove this, let $P$ be an arbitrary polynomial of even degree and positive leading coefficient, so there exist constants $x,y$ such that $P(z)$ is strictly increasing for $z > y$ and strictly decreasing for $z < x$ (this is because the derivative is an odd degree polynomial). So in $[x,y]$ , $P$ achieves some maximum value, say $M$ . So for any value $C> M$ , $P(z) - C$ can have at most two real roots (one greater than $y$ and one less than $x$ ), but since its continuous and takes every value sufficiently large for positive and negative values, it must have exactly two real roots and further, by picking $C$ sufficiently large, we can make the distance between the roots as large as we want, as desired. $\blacksquare$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a