Prove a polynomial has a nonreal root

Art of Problem Solving

AoPS Online

Contests & Programs AMC and other contests, summer programs, etc.

AMC and other contests, summer programs, etc.

3 M G

BBookmark VNew Topic kLocked

Contests & Programs AMC and other contests, summer programs, etc.

AMC and other contests, summer programs, etc.

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Prove a polynomial has a nonreal root

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: USAMO 2025/2

The post below has been deleted. Click to close.

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

407 posts

#1 h Thursday at 12:00 PM • 4 Y

Y by MathRook7817, NaturalSelection, LostDreams, NO_SQUARES

Let $n$ and $k$ be positive integers with $k<n$ . Let $P(x)$ be a polynomial of degree $n$ with real coefficients, nonzero constant term, and no repeated roots. Suppose that for any real numbers $a_0,\,a_1,\,\ldots,\,a_k$ such that the polynomial $a_kx^k+\cdots+a_1x+a_0$ divides $P(x)$ , the product $a_0a_1\cdots a_k$ is zero. Prove that $P(x)$ has a nonreal root.

Z K Y

The post below has been deleted. Click to close.

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

407 posts

#2 h Thursday at 12:02 PM • 3 Y

Y by MathRook7817, megarnie, LostDreams

Assume FTSOC $P$ has $n$ real roots. WLOG $P$ has leading coefficient $1$ so let $P(x)=:(x-r_1)\cdots(x-r_n)$ . WLOG $k=n-1$ , as otherwise we can take $Q:=(x-r_1)\cdots(x-r_{k+1})$ and deal with $Q$ instead of $P$ .

By the assertion, each $\frac{P(x)}{x-r_i}$ for $1\leq i\leq n$ has a coefficient equal to $0$ . Since $r_i\neq 0$ for all $i$ , this coefficient is not the leading or constant coefficient, so it has $k-1=n-2$ choices. By pigeonhole, there exists $1\leq i<j\leq n$ such that $Q(x):=\frac{P(x)}{x-r_i}$ and $R(x):=\frac{P(x)}{x-r_j}$ have no $x^\alpha$ term, for some $\alpha\geq 1$ . WLOG $i=n-1$ and $j=n$ . Hence
$\begin{align*} P(x)&=(x-r_1)\cdots(x-r_{n-2})(x-r_n)\\ Q(x)&=(x-r_1)\cdots(x-r_{n-2})(x-r_{n-1}). \end{align*}$ Then $P(x)-Q(x)=(r_{n-1}-r_n)(x-r_1)\cdots(x-r_{n-2})$ has no $x^\alpha$ term, so $A(x):=(x-r_1)\cdots(x-r_{n-2})$ has no $x^\alpha$ term since $r_{n-1}\neq r_n$ . Also, $r_{n-1}P(x)-r_nQ(x)=x(r_{n-1}-r_n)(x-r_1)\cdots(x-r_{n-2})$ has no $x^\alpha$ term so $A(x)$ has no $x^{\alpha-1}$ term.

Claim. $A(x)$ cannot have $n-2$ distinct real roots.
Proof. Suppose FTSOC $A(x)$ has $n-2$ distinct real roots. We claim that $A^{(m)}(x)$ , the $m$ th derivative of $A(x)$ , has $n-2-m$ distinct real roots for all $m\leq n-2$ . We proceed by induction on $m$ with the base case $m=0$ trivial.

Assume $A^{(m)}(x)$ has $n-2-m$ distinct real roots. Between every $2$ consecutive real roots there exists a local extremum, where $A^{(m+1)}(x)$ is $0$ . $A^{(m)}(x)$ has $n-2-m-1$ pairs of consecutive real roots so $A^{(m+1)}(x)$ has $n-2-(m+1)$ distinct real roots, completing the induction step.

$A^{(\alpha-1)}$ has no $x^{(\alpha-1)-(\alpha-1)}=x^0$ or $x^{\alpha-(\alpha-1)}=x$ term, so $0$ is a double root of $A^{(\alpha-1)}$ . However, all the roots of $A^{(\alpha-1)}$ are distinct and real, a contradiction. $\square$

This is a contradiction since $r_1,\,\ldots,\,r_{n-2}$ are distinct real numbers. Thus $P$ has a nonreal root. $\square$

This post has been edited 1 time. Last edited by KevinYang2.71, Yesterday at 12:12 AM

Z K Y

The post below has been deleted. Click to close.

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

982 posts

#3 h Thursday at 12:10 PM

Y by

tfw you wrote up a fakesolve that turned out to be correct

KevinYang2.71 wrote:

Claim. $A(x)$ cannot have $n-2$ distinct real roots.

how many points for claiming this but not proving it

Z K Y

The post below has been deleted. Click to close.

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

626 posts

#4 h Thursday at 12:11 PM • 1 Y

Y by KevinYang2.71

Assume for contradiction that all roots are real. Note that any divisor of $P$ with degree $>k$ will still satisfy the problem condition, hence we may WLOG assume $\deg P = k+1$ .

Denote the $d$ -th elementary symmetric sum of a set $S$ as $p_d(S)$ .

Reformulation of problem by Vieta wrote:

Distinct nonzero real numbers $r_1, \dots , r_{k+1}$ satisfy the following property: for each subset $S \subseteq \{r_1, \dots , r_{k+1}\}$ of size $|S|=k$ , there exists some $1 \le d_S < k$ such that $p_{d_S}(S) = 0$ .

Show this is impossible.

Since there are $k+1$ such subsets, by pigeonhole there are two distinct subsets $S_1$ and $S_2$ with $d_{S_1} = d_{S_2} \equiv d$ . WLOG let $S_1 = \{r_1, \dots , r_k\}$ and $S_2 = \{r_2, \dots , r_{k+1}\}$ , and denote $S_3 \equiv S_1 \cap S_2 = \{r_2, \dots , r_k\}$ ; then
$p_d (S_1) = p_d (S_2) \implies (r_{k+1}-r_1)p_{d-1}(S_3) = 0 \implies p_{d-1}(S_3) =0$ since $r_1 \neq r_{k+1}$ by assumption. Furthermore, we have
$0 = p_d(S_1) = r_1 p_{d-1}(S_3) + p_d(S_3) \implies p_d(S_3) = 0.$ But it turns out to be impossible to have $p_d(S_3) = p_{d-1}(S_3) = 0$ :

Lemma: A set of distinct nonzero real numbers cannot have two consecutive elementary symmetric sums both equal to zero. Equivalently, a polynomial with distinct nonzero roots cannot have two consecutive zero coefficients.

Proof: The second sentence follows by Descartes' rule of signs.

This post has been edited 2 times. Last edited by VulcanForge, Thursday at 12:15 PM

Z K Y

The post below has been deleted. Click to close.

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

407 posts

#6 h Thursday at 12:19 PM

Y by

scannose wrote:

tfw you wrote up a fakesolve that turned out to be correct

KevinYang2.71 wrote:

Claim. $A(x)$ cannot have $n-2$ distinct real roots.

how many points for claiming this but not proving it

2 for everything before using derivative maybe

Z K Y

The post below has been deleted. Click to close.

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

5538 posts

#7 h Thursday at 1:07 PM

Y by

This exists https://artofproblemsolving.com/community/c6h3486913_a_polynomial_problem

it's not the same problem, but it is essentially the main claim

Z K Y

The post below has been deleted. Click to close.

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

1740 posts

#8 h Thursday at 1:09 PM • 1 Y

Y by megarnie

Assume for the sake of contradiction has $P$ has $n$ real roots, say $r_1, r_2, \dots, r_n.$ If $n > k+1,$ we just need to consider a subset of these roots in the $n=k+1$ case to get our contradiction. Thus assume $n = k+1.$

Now for a subset $U \subset \{1,2,\dots,n\},$ we define $S_{k,U}$ to be the degree $k$ symmetric sum of the $a_i$ for all $i \in U.$ Also let $U_i = \{1,2,\dots, n\} \setminus \{i\}$ Then by Vieta's Formulas, we are given that for all $1 \le i \le k+1,$
$\begin{align*} S_{1,U_1} \cdot S_{2,U_1} \cdots S_{k,U_1} &=0, \\ S_{1,U_2} \cdot S_{2,U_2} \cdots S_{k,U_2} &=0, \\ \vdots \\ S_{1, U_{k+1}} \cdot S_{2,U_{k+1}} \cdots S_{k, U_{k+1}} &= 0. \end{align*}$
By PHP two of the numbers in the same column are equal to $0.$ Suppose WLOG that $S_{k, U_1} = S_{k, U_2} = 0.$ Some algebraic manipulation gives $S_{k-1, \{3,4,\dots,k+1\}} = S_{k-1, \{3,4,\dots,k+1\}} = 0.$ This means that the polynomial $Q(x) = \frac{P(x)}{(x-r_1)(x-r_2)}$ has two consecutive coefficients equal to $0.$

Claim: This cannot happen.
Proof: By Rolle's Theorem, the derivative $Q'(x)$ has $n-1$ distinct real roots as well, along with two consecutive coefficients which are equal to $0.$ We keep taking the derivative until we end up with something divisible by $x^2,$ contradiction as there can be no double roots.

Thus we have established a contradiction, hence done.

how many points would I get up to before the claim?

Z K Y

The post below has been deleted. Click to close.

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

302 posts

#9 h Thursday at 1:15 PM • 1 Y

Y by Mintylemon66

The following claim simplifies our problem a bit:
Claim:
It suffices to prove the statement for $n = k + 1$
Proof:
Assume the statement is true for $n = k + 1.$
Take a subset of $k + 1$ roots of $P.$ The set of degree $k$ polynomials generated by these $k + 1$ roots is a subset of the set of degree $k$ polynomials generated by all $n$ roots.

Thus, if we apply our hypothesis on this subset, we are get at least one of these roots is complex.
Now, we define a few things:
Assume $\ell \leq m.$ Say an equation is \textbf{\emph{type} $\ell$ of set $\{r_1, \dots, r_m\}$ } if the equation has form $\sum_{\stackrel{S\subseteq \{r_1, \dots, r_m\}}{|S| = \ell}}\prod_{r\in S}r = 0$ In other words, it is a cyclic sum of degree $\ell$ polynomials. We will call $\ell$ the degree. We will also say it is missing $r_j$ if $r_j \not\in \{r_1, \dots, r_m\}$
For example, $r_1r_2 + r_1r_3 + r_2r_3$ is type $3$ of $\{r_1, r_2, r_3\}.$
Claim:
If we prove that there can't be two equations of the same degree, we are done.
Proof:
First, note that we have $\binom{k + 1}{k} = k + 1$ equations. However, there are only $k$ possible degrees, which are $1, \dots, k$ (note that $k$ can't work, but this doesn't really matter). By PHP, this implies that there can't be two equations of the same degree.
\end{proof}
Claim:
There can't be two equations of the same degree
Proof:
WLOG, we assume $r_1, r_2$ are missing from the first and second equations, respectively. Also assume the degree is $0 < \ell < k.$ This gives:
\begin{equation}
r_2r_3\dots r_{\ell + 1} + r_2r_3\dots r_{\ell + 2} + \dots + r_{n - \ell + 1}\dots r_{n} = 0
\end{equation}
\begin{equation}
r_1r_3\dots r_{\ell + 1} + r_1r_3\dots r_{\ell + 2} + \dots + r_{n - \ell + 1}\dots r_{n} = 0
\end{equation}
From simple cancellation of comparing the two, we have that the type $\ell - 1$ equation of $\{r_3, \dots, r_{n}\}$ must be 0(since otherwise, $r_1 = r_2$ ):
\begin{equation}
r_3r_4\dots r_{\ell + 1} + r_3r_4\dots r_{\ell + 2} + \dots + r_{n - \ell + 1}\dots r_{n} = 0
\end{equation}
If we took $(1) - r_1\cdot (3),$ we get that the type $\ell$ equation of $\{r_3, \dots, r_n\}$ is 0, or:
\begin{equation}
r_3r_4\dots r_{\ell} + r_3r_4\dots r_{\ell + 1} + \dots + r_{n - \ell + 2}\dots r_{n} = 0
\end{equation}
This implies that there is a polynomial dividing $P$ that has two consecutive zero coefficients. Observe that by Rolle's Theorem, its derivative also has real roots. By simply inducting down on $k,$ we are done. The base case is obvious.

Z K Y

The post below has been deleted. Click to close.

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

815 posts

#10 h Thursday at 1:21 PM • 1 Y

Y by ihatemath123

This link also shows that a polynomial with distinct real roots can’t have $3$ consecutive coefficients in a geometric series. This could be another way to show that $2$ consecutive coefficients can’t be $0$ , but I think the normal approach is easier and more direct.

This post has been edited 1 time. Last edited by GrantStar, Thursday at 1:21 PM

Z K Y

The post below has been deleted. Click to close.

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

706 posts

#11 h Thursday at 1:36 PM

Y by

How many points for falling into fakesolve trap (I assume 0 cuz its just special case)

Z K Y

The post below has been deleted. Click to close.

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

23 posts

#12 h Thursday at 2:15 PM

Y by

how many points for saying proof by contradiction, none of the roots can be zero cause the constant is zero, and writing out all the polylomials in forms, stating that its probably descartes rules of signs or vietas and ending it from there

This post has been edited 1 time. Last edited by KadenC2026, Thursday at 2:18 PM
Reason: To clarify post

Z K Y

The post below has been deleted. Click to close.

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

320 posts

#13 h Thursday at 2:19 PM

Y by

i don't think u can just assume k = n-1. My proof used the fact that elementary symmetric sums are multilinear, so you can't have the same elementary symmetric sum (i.e. both the sum of the roots, both the product, or both the sum of pairwise products) of 2 sets of k roots with only 1 root in a given set but not the other be both 0.

Then I had to prove that max_2 (n,k) is less than (n choose k) / k-1. Is that true? Here max_2 (n,k) is the maximum possible size of a collection of k-element subsets of an n-element set such that no 2 subsets intersect in k-1 or k elements.

Z K Y

The post below has been deleted. Click to close.

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

7263 posts

#14 h Thursday at 2:20 PM • 1 Y

Y by scannose

k=n-1 is sufficient because otherwise you may take a polynomial Q(x) of degree k+1, with A|Q|P, and the pair of k, k+1 is done by above

Z K Y

The post below has been deleted. Click to close.

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

320 posts

#17 h Thursday at 2:23 PM

Y by

awesomeguy856 wrote:

k=n-1 is sufficient because otherwise you may take a polynomial Q(x) of degree k+1, with A|Q|P, and the pair of k, k+1 is done by above

oh no! i could have made this much easier! does my solution with the multilinear polynomials and max_2 work?

Z K Y

The post below has been deleted. Click to close.

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

11 posts

#18 h Thursday at 2:28 PM

Y by

Does anyone know how many “mohs” this question is, whatever that means?

Z K Y

The post below has been deleted. Click to close.

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

433 posts

#19 h Thursday at 2:30 PM

Y by

cushie27 wrote:

Does anyone know how many “mohs” this question is, whatever that means?

Math Olympiad Hardness Scale

Z K Y

The post below has been deleted. Click to close.

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

1727 posts

OronSH

#20 h Thursday at 2:30 PM • 1 Y

Y by Pengu14

cushie27 wrote:

Does anyone know how many “mohs” this question is, whatever that means?

ive heard 30

Z K Y

The post below has been deleted. Click to close.

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

7263 posts

#21 h Thursday at 2:32 PM • 6 Y

Y by OronSH, mineric, ihatemath123, peace09, scannose, trk08

ts pmo $\text{[math]}$

Z K Y

The post below has been deleted. Click to close.

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

11 posts

#22 h Thursday at 2:32 PM • 1 Y

Y by OronSH

OronSH wrote:

cushie27 wrote:

Does anyone know how many “mohs” this question is, whatever that means?

ive heard 30

I hope that means bronze medal cutoff shouldn’t be affected too much by this problem…

Z K Y

The post below has been deleted. Click to close.

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

266 posts

#23 h Thursday at 2:32 PM • 1 Y

Y by OronSH

Observe we only need to prove for $k = n-1$ ; indeed, $P$ either has no real roots, or it has a real root $r$ , and we can induct downwards by considering $P(x)/(x-r)$ until $k = n-1$ .

Let $\sigma_i(x_1, x_2, \dots, x_\alpha)$ denote the $i$ th elementary symmetric sum in the $\alpha$ varaibles $x_1$ , $\dots$ , $x_\alpha$ . Recall the identity $\sigma_i(x_1, x_2, \dots, x_n, y) = \sigma_i(x_1, x_2, \dots, x_n) + y\sigma_{i-1}(x_1, x_2, \dots, x_n).$
Now suppose FTSOC that $P$ has all real roots. Then as $\binom{n}{n-1} = n > n-1$ , there exist two subsets $S \subset\{1, 2, \dots, n\}$ with $|S| = n-1$ such that the corresponding coefficient of $\prod(x-r_i)$ which is $0$ is the same. In other words, we can order the roots of $P$ in such a way that for some $j$ ,
$\sigma_j(r_1, r_2, \dots, r_{n-2}, r_{n-1}) = \sigma_j(r_1, r_2, \dots, r_{n-2}, r_n) = 0.$ Using the identity above, and assuming all roots are distinct, we obtain that $\sigma_{i-1}(r_1, \dots, r_{n-2}) = 0$ , and similarly $\sigma_i(r_1, \dots, r_{n-2}) = 0$ .

By considering the polynomial $\prod_{i=1}^{n-2} (x-r_i),$ we are done by Descartes' rule of signs (a quick combinatorial argument shows that in fact we can only get up to $n-4$ real roots.)

Z K Y

The post below has been deleted. Click to close.

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

CrunchyCucumber

62 posts

CrunchyCucumber

#24 h Thursday at 2:34 PM

Y by

Does anyone know how day 1 was compared to previous years contests? I'm a first timer and I'm trying to see if I have a chance at mop.

Z K Y

The post below has been deleted. Click to close.

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

720 posts

#25 h Thursday at 2:44 PM

Y by

If I got everything in Kevin's (#2) solution before claiming $A(x)$ cannot have $n-2$ distinct real roots would that be $2$ partials?

Z K Y

The post below has been deleted. Click to close.

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

325 posts

#26 h Thursday at 2:52 PM

Y by

Suppose $P(x)$ had no nonreal roots. We can assume $P(x)$ has degree $k + 1$ , as we can always find a polynomial $Q(x) \mid P(x)$ such that $Q(x)$ has no nonreal roots. We can also assume $P(x)$ is monic by scaling. Also, the $k = 1$ case is trivial as the constant term must be nonzero, so fix $k \geq 2$ . Let the roots of $P(x)$ be $r_1, r_2, \dots, r_{k+1}$ .

Now consider the degree $k-1$ polynomials $Q_c(x) = \prod_{\stackrel{i=0}{i\neq c}}^k (x - r_i)$ for integers $1 \leq c \leq k$ . If $Q_c(x) = x^{k-1} + \alpha_{k-2}x^{k-2} + \cdots + \alpha_0$ , then for $Q_c(x)(x - r_{k+1})$ to have some coefficient equal to $0$ , expanding shows that we must have $r_{k+1} \in \left\{\alpha_{k-2}, \frac{\alpha_{k-3}}{\alpha_{k-2}}, \dots, \frac{\alpha_0}{\alpha_1}\right\}.$
There are at most $k - 1$ values in this set. Fix the value of $r_{k+1}$ . Now consider the degree $k - 2$ polynomials $Q_{c,d}(x) = \gcd(Q_c(x), Q_d(x)) = \prod_{\stackrel{i=0}{i\neq c,d}}^k (x - r_i)$ . If $Q_{c,d}(x) = x^{k-2} + b_{k-3}x^{k-3} + \cdots + b_0$ and $Q_{c,d}(x)(x-s) = x^{k-1} + B_{k-2}x^{k-2} + \cdots + B_0$ , then for any fixed $i$ , $\frac{B_i}{B_{i+1}} = r_{k+1}$ is a linear equation in $s$ .

Case 1: For all $i$ , $\frac{B_i}{B_{i+1}} = r_{k+1}$ has at most one solution for $s$ . Then, this means that $Q_{c,d}(x)(x - r_c) = Q_d(x)$ and $Q_{c,d}(x)(x - r_d) = Q_c(x)$ must have different $i$ (if one exists) such that $\frac{B_i}{B_{i+1}} = r_{k+1}$ . But there are only $k - 1$ such indices of $i$ and $k$ polynomials, so there exists some $c$ such that $Q_c(x)(x - r_{k+1})$ has no coefficient equal to $0$ , done.

Case 2: If there exists some $i$ such that $\frac{B_i}{B_{i+1}} = r_{k+1}$ has infinite solutions in $s$ , then since $B_i = b_{i-1} - sb_i$ and $B_{i+1} = b_i - sb_{i+1}$ and rearranging gives $(r_{k+1}b_{i+1} - b_i)s = (r_{k+1}b_i - b_{i-1})$ , we must have $r_{k+1}b_{i+1} - b_i = r_{k+1}b_i - b_{i-1} = 0$ , thus $b_{i+1}, b_i, b_{i-1}$ forms a geometric series of ratio $r_{k+1}$ .

Thus $Q_{c,d}(x) = R(x) + bx^{i+1} + brx^i + br^2x^{i-1}$ and so $Q_{c,d}(rx) = R(rx) + br^{i+1}x^{i+1} + br^{i+1}x^i + br^{i+1}x^{i-1}$ . We now claim that this polynomial must have a complex root since three consecutive coefficients are equal.

Consider $P(x)Q_{c,d}(x)(x-1) = xQ_{c,d}(x) - Q_{c,d}(x)$ . Notice this has two consecutive coefficients that are equal to $0$ . Now apply this lemma and we are done.

How many points for completely missing the existence of case 2 in contest (Claim: linear equation -> 1 solution)? I saw the case but with only 15 minutes left and did not have time to determine that it was useful enough to write up to the three consecutive coefficients in geometric progression and conjecture that it must have a complex root.

Z K Y

The post below has been deleted. Click to close.

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

342 posts

#27 h Thursday at 2:56 PM

Y by

if I did everything else, except forgetting to state Pigeonhole and k + 1, how many partials would that be

VulcanForge wrote:

Since there are $k+1$ such subsets, by pigeonhole there are two distinct subsets $S_1$ and $S_2$ with $d_{S_1} = d_{S_2} \equiv d$ . WLOG let $S_1 = \{r_1, \dots , r_k\}$ and $S_2 = \{r_2, \dots , r_{k+1}\}$ , and denote $S_3 \equiv S_1 \cap S_2 = \{r_2, \dots , r_k\}$ ; then

Z K Y

The post below has been deleted. Click to close.

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

982 posts

#28 h Thursday at 3:00 PM

Y by

it's funny how half of the posts on this thread asked about partials (ok half is an exaggeration but)
this year seems harder than the last

This post has been edited 1 time. Last edited by scannose, Thursday at 3:01 PM

Z K Y

The post below has been deleted. Click to close.

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

5538 posts

#29 h Thursday at 3:01 PM

Y by

scannose wrote:

it's funny how half of the posts on this thread asked about partials
this year seems harder than the last

I disagree, I thought p2 on 2024 amo was quite a bit harder

however this could also be because im biased and not great at combo

@below p3 apparently had more solves this year

difficulty in general depends a lot on your subject preference

This post has been edited 2 times. Last edited by megarnie, Thursday at 3:04 PM

Z K Y

The post below has been deleted. Click to close.

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

982 posts

#30 h Thursday at 3:02 PM

Y by

megarnie wrote:

I disagree, I thought p2 on 2024 amo was quite a bit harder

however this could also be because im biased and not great at combo

even if p2 wasn't harder, p3 was

edit: oh womp womp

This post has been edited 1 time. Last edited by scannose, Thursday at 3:04 PM

Z K Y

The post below has been deleted. Click to close.

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

169 posts

deduck

#31 h Thursday at 11:05 PM • 1 Y

Y by KevinYang2.71

i thought this was easier than p3 but maybe that's because i was being an idiot on the other one and scared of it

just stare at problem until u get two polynomials with $n$ roots from a set of $n+1$ distinct roots that have the same coefficient equal to $0$ , note that either the two sets of $n$ roots are the same, which is false, or the $x$ th and $x+1$ th symmetric sum involving $n-1$ roots that they share in common is both $0$ . However this implies that there's $2$ consecutive coefficients equal to $0$ when u write it the standard way, but it's obviously false it can happen if all roots are distinct and real

this is my last olympiad problem , i don't know what made me waste the better part of my childhood wasting my time on these while people more gifted or cheaters were going to beat me in the end so i didnt even get to do a single olympiad problem in olympiad

Z K Y

The post below has been deleted. Click to close.

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

1566 posts

#32 h Thursday at 11:31 PM

Y by

wait wtf i got to the two consecutive coefficients are zero and wrote “now i don’t know what to do” even though i just needed a literal fifteen words saying “we repeatedly differentiate until we get a double root, which is impossible by Rolle’s Theorem.”

grrrrrrrrr how many points do you think i get

if i miss mop b/c of this i’ll be sad

Z K Y

The post below has been deleted. Click to close.

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

3439 posts

#33 h Thursday at 11:39 PM

Y by

@above 0 $~$

Z K Y

The post below has been deleted. Click to close.

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

1740 posts

#34 h Yesterday at 1:02 AM

Y by

solasky wrote:

wait wtf i got to the two consecutive coefficients are zero and wrote “now i don’t know what to do” even though i just needed a literal fifteen words saying “we repeatedly differentiate until we get a double root, which is impossible by Rolle’s Theorem.”

grrrrrrrrr how many points do you think i get

if i miss mop b/c of this i’ll be sad

im in a similar situation as you oops
some orz people on discord said it may be worth 2 points

Z K Y

The post below has been deleted. Click to close.

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

18 posts

#35 h Yesterday at 1:04 AM

Y by

I have the opposite issue compared to many. I proved the 2 consecutive coefficients part, but I failed the pigeonhole part since I didn't realize I could WLOG $k=n-1$ . I ended up writing there were at least $\left\lceil\frac{\binom{n}{k}}{k-1}\right\rceil$ subsets of $k$ roots sharing a $0$ coefficient by Pigeonhole, then trying to show two of these subsets shared $k-1$ roots, thus implying the two consecutive zero coefficients (which failed miserably). Anyone know how many points this would be?

Z K Y

The post below has been deleted. Click to close.

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

54 posts

#36 h Yesterday at 1:29 AM • 1 Y

Y by Ilikeminecraft

Here, we have a solution without WLOG $k=n-1$ , without Descartes rule of signs, without Rolle, but is somehow not terrible?

Let $e_k$ denote the degree $k$ elementary symmetric polynomial.

Suppose for the sake of contradiction that all roots of $P(x)$ were real. Let the roots be $r_1,r_2,\dotsc,r_n$ . Let $R$ be the set of roots. Then for every subset $S$ of $k$ roots, $e_i(S)=0$ for some $1\le i\le k-1$ .

Define two subsets of $k$ elements to be adjacent if they share $k-1$ elements.
Lemma. If $\mathcal F$ is a family of $k$ -element subsets of $R$ such that no two are adjacent, then $|\mathcal F|\le\frac{1}{k+1}\binom nk$ .
Proof. Every set $T$ in $\mathcal F$ is adjacent to exactly $k(n-k)$ sets outside of $\mathcal F$ because we may pick any element of $T$ to remove and any root not in $T$ to add. Meanwhile, any set $U$ not in $\mathcal F$ is adjacent to at most $n-k$ sets in $\mathcal F$ because when we remove an element of $U$ and add a root not in $U$ , the additional roots for the adjacent sets in $\mathcal F$ must be distinct. Counting then gives the desired result.

Now define $\mathcal F_i$ to be the family of $k$ -element subsets of roots such that $e_i$ vanishes. Then there are $k-1$ such families, and every size $k$ subset of the roots is in at least one family, so one family must have size at least $\frac{1}{k-1}\binom nk$ . Therefore, at least one family must contain two adjacent subsets. This implies that there are roots $r_1,r_2,\dotsc,r_k,r_k'$ such that
$e_i(r_1,r_2,\dotsc,r_k)=e_i(r_1,r_2,\dotsc,r_{k-1},r_k')=0.$ Now we expand these by writing
$e_i(r_1,r_2,\dotsc,r_{k-1})+r_ke_{i-1}(r_1,r_2,\dotsc,r_{k-1})=e_i(r_1,r_2,\dotsc,r_{k-1})+r_k'e_{i-1}(r_1,r_2,\dotsc,r_{k-1})=0,$ and since $r_k\neq r_k'$ , we have
$e_i(r_1,r_2,\dotsc,r_{k-1})=e_{i-1}(r_1,r_2,\dotsc,r_{k-1})=0.$
Suppose that $\{r_1,r_2,\dotsc,r_{k-1}\}$ is a set of real numbers such that $e_i(r_1,r_2,\dotsc,r_{k-1})=e_{i-1}(r_1,r_2,\dotsc,r_{k-1})=0$ for some $i$ , but no strict subset has this property. It suffices to show that such a set cannot exist.

Now we perform a bit of further expansion
$e_i(r_1,r_2,\dotsc,r_{k-2})+r_{k-1}e_{i-1}(r_1,r_2,\dotsc,r_{k-2})=e_{i-1}(r_1,r_2,\dotsc,r_{k-2})+r_{k-1}e_{i-2}(r_1,r_2,\dotsc,r_{k-2})=0,$ from which we may deduce that
$e_i(r_1,r_2,\dotsc,r_{k-2})e_{i-2}(r_1,r_2,\dotsc,r_{k-2})=e_{i-1}(r_1,r_2,\dotsc,r_{k-2})^2.$
By minimality, none of $e_i$ , $e_{i-2}$ , or $e_{i-1}$ can vanish, for then two consecutive elementary symmetric polynomials must vanish. By "On the nonnegativity of generalized discriminants of quadratics",
$e_{i-1}(r_1,r_2,\dotsc,r_{k-2})^2\ge \frac{i(k-i)}{(i-1)(k-i-1)}e_i(r_1,r_2,\dotsc,r_{k-2})e_{i-2}(r_1,r_2,\dotsc,r_{k-2}).$ Since $e_{i-1}(r_1,r_2,\dotsc,r_{k-2})^2$ is strictly positive, we have a contradiction.

This post has been edited 1 time. Last edited by golue3120, Yesterday at 1:32 AM

Z K Y

The post below has been deleted. Click to close.

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

1457 posts

#37 h Yesterday at 5:34 AM • 2 Y

Y by KevinYang2.71, Pengu14

This problem is kinda funny, I guess giving a rating is hard.
So FTSOC $P$ has $n$ real roots and WLOG it is monic and WLOG $k=n-1$ by simply shifting with the other monomials then define $P(x)$ as $(x-r_1) \cdots (x-r_n)$ then it happens that all of $\frac{P(x)}{x-r_i}$ for $1 \le i \le n$ happen to have one coefficient equal to $0$ , since there is at most $n-2$ choices for these so by pigeonhole there exists $i \ne j$ such that $\frac{P(x)}{x-r_i}$ and $\frac{P(x)}{x-r_j}$ are missing the same coefficient $x^{\ell}$ for $\ell \ge 1$ (this is because none of the roots are equal and none can be zero), let these be called $A(x), B(x)$ respectively and let $i,j$ be $n,n-1$ (it doesn't matter anyway lmao), then we have that $A(x)=(x-r_1) \cdots (x-r_{n-1})$ and $B(x)=(x-r_1) \cdots (x-r_{n-2})(x-r_n)$ which the means that $A(x)-B(x)=(r_n-r_{n-1})(x-r_1) \cdots (x-r_{n-2})$ is missing the $x^{\ell}$ coefficient but also notice that $r_nA(x)-r_{n-1}B(x)=(r_n-r_{n-1})x(x-r_1) \cdots (x-r_{n-2})$ is missing the $x^{\ell}$ coefficient but since $r_n \ne r_{n-1}$ then we do in fact have that $A(x)-B(x)$ is missing both the $x^{\ell}$ and $x^{\ell-1}$ coefficient. (Now we can wlog say $\ell$ is minimal).
Call it $C(x)$ then it has $n-2$ real roots, is $\deg C=n-2$ but also it has two consecutive missing coefficients so write it as $x^2D(x)+E(x)$ (essy to check that if $n=2$ this is trivial and if $n=3$ then you have cuadratics of the form $x^2+b$ which shows pairwise sum of roots is zero and thus all are zero, a contradiction!), so for $n \ge 4$ notice that $n-4=\deg D$ and that you can set it so that least degree term on $D$ is greater than $\deg E$ .
Now from derivative analytical definition and propeties we can check graphically that counting multiplicity a polynomial has all its roots real if and only if the derivative does as well, so now take the $\deg E+1$ -th derivative of $Q$ , then $Q^{(\deg E+1)}(0)=0$ but also $Q^{(\deg E+2)}(0)=0$ and these polynomials must have all of their roots real by chaining the fact that $Q$ does follow this so because of minimality of $\ell$ , it happens that $E$ has a non-zero leading coefficient and thus if it were the zero polynomial we are done by the same argument as if it weren't which we will see now.
So let $R(x)=Q^{(\deg E)}(x)=c(x-q_1) \cdots (x-q_m)$ , now focus on the product of monomials and call it $R_1(x)$ , then it happens that $\frac{R_1'(x)}{R_1(x)}=\sum_{i=1}^{m} \frac{1}{x-q_i}$ and thus by taking derivative w.r.t. $x$ it happens that $\frac{R_1'(x)^2-R_1''(x)R_1(x)}{R_1(x)^2}=-\sum_{i=1}^{m} \frac{1}{(x-q_i)^2}$ for all $x \ne q_j$ for $1 \le j \le m$ , however clearly none of the roots are zero once again but replacing $x=0$ we have LHS is zero while RHS isn't, contradiction!.
Therefore $P$ must have a non-real root thus we are done :cool:

:cool:

.

Z K Y

The post below has been deleted. Click to close.

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

6 posts

#38 h Yesterday at 6:54 PM

Y by

How many points for proving it suffices to prove k=n-1? I made a mistake for the part where I prove k=n-1 works, so I don’t think I’m getting any credit there.

This post has been edited 2 times. Last edited by Pomansq, Yesterday at 6:56 PM

Z K Y

The post below has been deleted. Click to close.

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

170 posts

#39 h Yesterday at 7:17 PM

Y by

This problem is certainly based on the following lemma:
Lemma: A polynomial with only real distinct roots can't have two consecutive zero coefficients
Proof: Let the polynomial be $P$ and the coefficients be for $x^k,x^{k+1}$ . Then $P^{(k)}$ is a polynomial which must have only real distinct roots, but it is divisible by $x^2$ , a contradiction.

Now to the problem. We consider the contrary. Take any $k+1$ of this $n$ roots, say they are $r_1,\ldots,r_{k+1}$ . Consider the polynomials of the form $\frac{(x-r_1)\ldots (x-r_{k+1})}{x-r_i}$ . $P$ is divisible by it, hence it has a zero coefficient. But its coefficients are elementary symmetric polynomials in variables $r_1,r_2,\ldots,r_{k+1}$ . Also, it is not the product since none of the roots is zero. So there are only $k-1$ options for the size of the elementary polynomial, and $k+1$ polynomials, by Pigeonhole there is a repetition. So $\sigma_i(r_1,\ldots,r_{k-1},r_k)=\sigma_i(r_1,\ldots,r_{k-1},r_{k+1})=0$ . But $\sigma_i(r_1,\ldots,r_{k-1},x)=x\sigma_{i-1}(r_1,\ldots,r_{k-1})+\sigma_i(r_1,\ldots,r_{k-1})$ , and as it is a linear function with two distinct roots, we must have $\sigma_{i-1}(r_1,\ldots,r_{k-1})=\sigma_i(r_1,\ldots,r_{k-1})$ . This contradicts the Lemma. Thus, $P$ must have a nonreal root.

Z K Y

The post below has been deleted. Click to close.

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

33 posts

#40 h Yesterday at 10:19 PM

Y by

How much do I get if I proved everything but assumed n=k+1 without justifying? I was a bit confused by the wording

Z K Y

The post below has been deleted. Click to close.

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

awesomeming327.

1668 posts

awesomeming327.

#41 h Today at 2:58 AM

Y by

Assume on the contrary. We prove the result for $k=n-1$ . This is equivalent to the original problem because we can simply remove some of the roots of $P$ to reduce to this new problem anyway.

Let $P(x)=(x-r_1)(x-r_2)\dots(x-r_n)$ for some distinct nonzero roots $r_1$ , $r_2$ , $\dots$ , $r_n$ . Let $P_i(x)$ be $(x-r_1)\dots(x-r_{i-1})(x-r_{i+1})\dots(x-r_n)$ , which must have a zero coefficient. Note that there are $n$ polynomials $P_1$ , $P_2$ , $\dots$ , $P_n$ and $n-2$ coefficients at which this zero coefficient can appear. Therefore, there exists two polynomials (WLOG let them be $P_n$ and $P_{n-1}$ ) such that $P_n$ and $P_{n-1}$ both have a zero as an $x^i$ coefficient.

Let $(x-r_1)(x-r_2)\dots(x-r_{n-2})$ be $Q(x)$ . We have
$\begin{align*}P_n-P_{n-1} &= (x-r_{n-1})Q(x)-(x-r_n)Q(x)=(r_n-r_{n-1})Q(x) \\ r_nP_n-r_{n-1}P_{n-1} &= (r_nx-r_{n-1}r_n)Q(x)-(r_{n-1}x-r_{n-1}r_n)Q(x)=(r_n-r_{n-1})xQ(x)\end{align*}$ both of which have zero as an $x^i$ coefficient, which means that $Q(x)$ has a zero in both its $x^i$ and $x^{i-1}$ coefficients. We now prove the following claim, which finishes the problem:

Claim 1: Let $Q(x)=(x-r_1)(x-r_2)\dots(x-r_n)$ be a polynomial with distinct nonzero real roots. Then $Q(x)$ may not have two consecutive zero coefficients.

Let $R(x)$ be a polynomial with $r$ distinct roots. Then, $R'(x)$ has $r-1$ distinct roots because between each two roots of $R(x)$ , there will be a relative extrema. Therefore, if we keep taking derivatives of $Q$ , there will always be $\operatorname{deg} Q$ distinct roots. But since there are two consecutive zero coefficients, eventually some multiple derivative of $Q$ will have both its constant and linear coefficients zero, which means that it has a double root at $0$ , impossible.

This post has been edited 2 times. Last edited by awesomeming327., Today at 2:58 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a