Polynomial approximation and intersections

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

Polynomial approximation and intersections

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: All Russian 2025 10.6

The post below has been deleted. Click to close.

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

209 posts

egxa

#1 h Apr 18, 2025, 5:11 PM

Y by

What is the smallest value of $k$ such that for any polynomial $f(x)$ of degree $100$ with real coefficients, there exists a polynomial $g(x)$ of degree at most $k$ with real coefficients such that the graphs of $y = f(x)$ and $y = g(x)$ intersect at exactly $100$ points?

This post has been edited 1 time. Last edited by egxa, Apr 18, 2025, 5:21 PM

Z K Y

The post below has been deleted. Click to close.

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

1519 posts

#2 h Apr 19, 2025, 3:48 AM

Y by

Recall the well known analysis fact that if a polynomial has exactly $n$ real roots counting multiplicity then its derivative has exactly $n-1$ real roots counting multiplicity. So if $k \le 97$ the considering the $98$ -th derivative of $f-g$ gives that for any three given reals $a,b,c$ we must have that $ax^2+bx+c$ always has two real root if $f-g$ had exactly $100$ different roots, thus a contradiction by picking suitable $a,b,c$ (my example would just be $a,c>0$ and $b=0$ lol).
Now we will show $k=98$ works, first clean all the polynomial of degree $98$ inside $f$ using $g$ and from there many a suitable pick, in fact $100$ does not matter so we can prove a slightly stronger claim using induction.
We show that it is possible to construct a polynomial of degree $n$ where only coefficients $x^{n}, x^{n-1}$ are not in our control, so that the polynomial has all real roots with no multiplicity and none of them are zero.
For $n=2$ we can obviously shift the parabola by a constant acording to what is needed due to discriminant criteria so we should be fine here, due to continuity in fact you can just avoid a root being zero or the resulting parabola being tangent to the $x$ axis, for $n=3$ you have something unfree of the form $x^2(ax+b)$ and so you pick some $c(ax+b)+d$ on the free part where $c,d$ have freedom acording to needs like if $b=0$ then $d \ne 0$ and could just be suficiently small given we put $c<0$ to have two roots and that in order to not have repeated roots or the cubic being tangent to the $x$ axis at any moment (continuity yay).
For $n=4$ you basically have control over a depressed cubic upon doing a similar setup as seen above just shift everything by a small constant at the end to satisfy all the given conditions needed and now we will show this is the kind of work you have to do.
Suppose it was true for $n=\ell$ then we prove it for $n=\ell+1$ , notice the not free term is $x^{\ell}(ax+b)$ so we just use the free term to focusing on a polynomial of the kind $x^{\ell}+q(x)$ for $\deg q \le \ell-2$ , notice here it might happen that $-b \cdot a^{-1}$ is a root twice then we just shift by a very small constant as needed whether is above or below, one of them should work by continuity and IVT, since have $0$ as a root is only a one thing thing on a small interval we can also use continuity to avoid this and still satisfy the no double roots or more condition, hence by using the inductive hypothesis this is also completed and thus our claim is proven.
Just throw the claim and use a suitable $g$ to win, and thus we are done :cool:

:cool:

.

This post has been edited 1 time. Last edited by MathLuis, Apr 19, 2025, 3:49 AM

Z K Y

The post below has been deleted. Click to close.

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

8 posts

#3 h Apr 29, 2025, 11:43 AM

Y by

We claim that the answer is $\boxed{k=98}$ .
Claim 1: $k>97$
Assume the contrary. there exists a polynomial $g(x)$ with degree less than $98$ such that $f(x)-g(x)$ has 100 roots for $f(x)=x^100$ . Define $k$ as the degree of $g(x)$
Define a_{1},...,a_{k} such that $f(x)-g(x)=x^{100}+a_{k}x^k+...+a_{0}$ . Define $r_{1},...,r_{100}$ as the real roots of $f(x)-g(x)$ .
By vieta's formula since the coefficient of $x^{99}$ and $x^{98}$ is equal to $0$ : $\sum_{i=1}^{100}r_{i} = 0$ and $\sum_{i<j}^{}r_{i}r_{j} = 0 \implies \sum_{i=1}^{100}r_{i}^2 = 0 \implies r_{i}=0 \implies f(x)-g(x)=0$ which is a contradiction. It follows that $k>97$ .
Claim 2: $k=98$
We can basically alter all the coefficients of $f(x)-g(x)$ except the coefficients of $x^{100}$ and $x^{99}$ so by vieta's formula our only restriction is the sum of the roots of the polynomial. So we just need to pick 100 arbitrary pairwise different real numbers such that their sum is equal to $-\frac{a_{99}}{a_{100}}$ with $a_{99}$ being the coefficient of $x^{99}$ and $a_{100}$ being the leading coefficient. Obviously this is possible. From here we just alter the other coefficients so that each one of the coefficients becomes equal to the coefficients of the polynomial that has all these $100$ numbers as roots multiplied by $a_{n}$ and so we are done. $\blacksquare$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a