Suppose $a_0,\ldots, a_{100}$ are positive reals. Consider the following polynomial for each $k$ in $\{0,1,\ldots, 100\}$: $$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., $a_{100+i}=a_{i-1}$ for any $i$ in $\{1,2,\dots, 100\}$. Show that it is impossible that each of these $101$ polynomials has all its roots real. Proposed by Prithwijit De
Problem
Source: INMO 2023 P2
Tags: algebra, Polynomials, inequalities, INMO, INMO 2023
15.01.2023 14:56
Assume to the contrary that all of the polynomials have all real roots. Clearly, all roots must be negative real numbers. For a polynomial $P$, denote by $\sigma_i(P)$ the sum of products of roots of $P$ with $i$ of them taken at a time, for $i=1, 2, \dots, \text{deg} \, P$. Denote by $P_k$, the $k$-th cyclic polynomial for each $k=0, 1, \dots, 100$. Now $-\sigma_1(P_k)=100\frac{a_{99+k}}{a_{100+k}}=100\frac{a_{k-2}}{a_{k-1}}$ and $\sigma_{100}(P_k)=\frac{a_k}{a_{k-1}}$ by Vieta's relations. By AM-GM inequality on the negative of roots of $P_k$, we get $\left(\frac{a_{k-2}}{a_{k-1}}\right)^{100} \geq \frac{a_k}{a_{k-1}}$. Multiplying all such inequalities as $k$ varies, gives $1 \geq 1$, so all of them must be equalities, and for each $k$, all roots of $P_k$ must be equal to $\frac{a_{k-2}}{a_{k-1}}$. Many ways to finish from here: $\sigma_2(P_k)=\binom{100}{2}\left(\frac{a_{k-2}}{a_{k-1}}\right)^2$ by equal roots, and $\sigma_2(P_k)=\frac{a_{k-3}}{a_{k-1}}$ by Vieta's relations, so multiplying all these shows that $\binom{100}{2}^{100}=1$, which is absurd. Alternately, let $x_k=\frac{a_k}{a_{k-1}}$, then $x_k = \left(\frac{1}{x_{k-1}}\right)^{100}$ follows from the equality. Following cyclically, we get $x_k=x_k^{\pm 100^{101}}$ which forces each $x_k=1$, hence $a_0=\dots=a_{100}$. So we just need to show that the polynomial $x^{100}+100x^{99}+x^{98}+\dots+x^2+x+1$ has not all roots real (and equal). Note that the sum of squares of roots is negative, or that $-1$ is not a root of this polynomial, to conclude.
15.01.2023 16:01
We show that it's only possible for $n=1$ where $n$ is degree of polynomial divided by $2$. My solution: Let $s_k=\frac{a_{k}}{a_{k-1}}$. Let the polynomial for a particular $k$ be $P_k(x)$. Now, let the roots of $P_k(x)$ be $-\alpha_{1,k}$, $-\alpha_{2,k}$, $\dots$, $-\alpha_{2n,k}$. Observe that $\alpha_{i,j}>0$ since none of the polynomials have non negative roots. (The polynomials evaluate to a positive number at non-negative numbers due to positive coefficients.) Now, by Vieta's formula, we have $\frac{\sum_{i=1}^{2n} \alpha_{i,k}}{2n}=\frac{1}{s_{k-1}}$ and $\prod_{i=1}^{2n} \alpha_{i,k}=s_k$. Now, by AM-GM, we get that \[\frac{1}{s_{k-1}^{2n}}\ge s_k\] Multiplying over all $k\in \{0,1,\dots, 2n\}$, we get $1\ge 1$ implying that all the inequalities are actually equalities i.e. $s_{k-1}^{2n}s_{k}=1$ for all $i$ and $\alpha_{i,k}=\alpha_{j,k}$ for all $i$, $j$. Thus, we have $\frac{1}{s_{k-1}}=\alpha_{i,k}$. Now, let $m$ be such that $s_m$ is maximum. Clearly $s_m\ge 1$ since $\prod s_i=1$. Now, we have $s_{m+1}=\frac{1}{s_m^{2n}}\implies s_{m+2}=s_m^{4n^2}$ but if $s_m>1$ then $s_{m+2}>s_m$ which is not possible. Thus, $s_m=1\implies s_i=1\forall i$. Thus, $a_i=a_j=a$ for all $i,j$ for some $a\in \mathbb{R}^+$. Thus, we get all $\alpha_{i,k}=1$ for all $i,k$. Thus, we have $P_k(x)=a(x+1)^{2n}$. If $n=1$, this is okay and if $n>1$, then we get $a=\binom{2n}{2}a$ but this is not possible. Thus, we are done. $\square$
15.01.2023 16:13
Suppose it was possible. Then fix a $k$ and note that every real of $P_k(x)$, the polynomial, must be negative, so say they're $-x_1, -x_2, \cdots, -x_{100}$. Then we have that $\sum_{i=1}^{100} x_i = \frac{100a_{k+99}}{a_{k+100}}$ and $\prod_{i=1}^{100} x_i = \frac{a_k}{a_{k+100}}$. Since all of them are positive, by AM-GM, we get that $\left(\frac{a_{k+99}}{a_{k+100}} \right)^{100} \geqslant \frac{a_k}{a_{k+100}}$ for all $k$. Now say $a_j$ is the minimal one among all of them and pick $k \equiv j-99 \pmod{101}$. This forces equality to hold everywhere and implies $a_j = a_{j+1}$ and so all the $a_i$ are equal. Further for equality to hold, AM-GM equality must have held so all roots must have been equal and since they have sum $-100$, each of them must be $-1$. But $P(-1) = 98 \neq 0$, so this is not possible either, done.
15.01.2023 16:24
bruh this was so scam i thought this involved some super advanced stuff
15.01.2023 16:55
Can we add all the hundred polynomials and then derive a solution
15.01.2023 19:48
Another solution with a slightly different finish I had in contest Let $P_k$ denote the polynomial $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$. Notice that all roots of $P_k$ are negative. Claim: $\left( \frac{a_{i}}{a_{i+1}} \right)^{100} = \left(\frac{a_{i+2}}{a_{i+1}} \right)$ for all $i$ indices taken mod $101$ Proof: Let the roots of $P_k$ be $\alpha_1, \alpha_2 \cdots \alpha_{100}$ then since $\alpha_j$ is negative $\forall j$ we have that $$\sum_{j=1}^{100} (-\alpha_j) \geq 100 \sqrt[100]{\prod_{j=1}^{100} |\alpha_j|} \implies \left( \frac{a_{99+k}}{a_{100+k}} \right)^{100} \geq \left( \frac{a_k}{a_{100+k}} \right) = \left( \frac{a_{101+k}}{a_{100+k}} \right)$$Taking the product over all $k$ we have $1 \geq 1$ which means equality must hold at every stage which gives the desired claim Suppose $\forall i , a_i \neq a_{i+1}$ indices taken $\pmod{101}$ Then from our claim we must have that their must not exist a tuple $\left(a_i, a_{i+1}, a_{i+2} \right)$ such that this tuple is either strictly increasing or strictly decreasing. Case (i) : $a_0 > a_1$ Proof: In this case we must have that $a_i > a_{i+1},$ $\forall i$ even and $a_i < a_{i+1},$ $\forall i$ odd. But we note that $a_{100} > a_0 > a_1$ which quickly gives us a contradiction Case (ii) : $a_0 < a_1$ Proof: In this case we must have that $a_i < a_{i+1},$ $\forall i$ even and $a_i > a_{i+1},$ $\forall i$ odd. Again we note that $a_{100} < a_0 < a_1$ which again gives a contradiction. Hence we must have $a_i = a_{i+1}$ for some $i$. Inducting with our claim we quickly achieve $a_i = a_{i+1}$ for all $i$. Claim: The polynomial $x^{100} + 100x^{99} + x^{98} \cdots 1$ does not have all roots real Proof: FTSOC assume it has all roots real. Again we have all roots negative. Hence if $x_1, x_2 \cdots x_{100}$ be the roots of the polynomial then $$\sum_{j=1}^{100} (-x_j) \geq 100 \sqrt[100]{\prod_{j=1}^{100} |x_j|} \implies 1 \geq 1$$which means $x_j$'s are equal $\implies$ they are all equal to $-1$. But clearly $-1$ is not the only root with which we are done $\qquad \blacksquare$
15.01.2023 22:20
here's my write-up: denote $P_{k}(x)=a_{100+k}x^{100}+100a_{99+k}x^{99}+a_{98+k}x^{98}+a_{97+k}x^{97}+\cdots+a_{2+k}x^2+a_{1+k}x+a_{k}$ $\forall$ $k\in \{0,1,2,3,\cdots,100\}$ Claim:- all roots of $P_{k}(x)$ are non-real pf:-FTSOC it's all roots are real now if $a_{i}\in \mathbb{R^{+}}$ we have roots of $P_{k}(x)$ to be $-\alpha_{k,1},-\alpha_{k,2},\cdots -\alpha_{k,100}$ where $\alpha_{k,i}>0$ now $\sum_{i=1}^{100} \alpha_{k,i}=100\cdot \left (\frac{a_{99+k}}{a_{100+k}}\right)$ and $\prod_{i=1}^{100} \alpha_{k,i}=\frac{a_{k}}{a_{100+k}}$ from $AM\ge GM$ we observe : $\left(\frac{a_{99+k}}{a_{100+k}}\right)^{100}\ge \frac{a_{k}}{a_{100+k}}$, now since $k$ varies from $0$ to $100$ we oberve: $\prod_{k=0}^{100}\left(\frac{a_{99+k}}{a_{100+k}}\right)^{100} \ge \prod_{k=0}^{100} \frac{a_{k}}{a_{100+k}}\implies \left(\frac{a_{99}}{a_{200}}\right)^{100}\ge 1$ but since we have $a_{99}=a_{200}$ we get $1\ge 1$ which forces equality hence $a_{j}=a_{j+1}$ $\forall j$ $\in$ $\{k,k+1,k+2,\cdots , k+99\}$ so we get $\sum_{i=1}^{100} \alpha_{k,i}=100$ and $\prod_{i=1}^{100} \alpha_{k,i}=1\implies \alpha_{k,1}=\alpha_{k,2}=\cdots \alpha_{k,100}=\beta$ , for some $\beta \in \mathbb{R^{+}}$ so we have $P_{k}(x)=\beta(x+1)^{100}$ also we had $a_{100+k}=a_{99+k}=a_{98+k}=\cdots =a_{k}$ which is not true for $P_{k}(x)$ hence contradiction and claim follows $\blacksquare$
16.01.2023 08:07
Unless I am crazy, my solution does not need to use the factor 100. Let $r_1, ...r_{100}$ be the roots, then by Vieta's formula \[ \sum \frac{1}{r_i} = -\frac{a_1}{a_0}, \quad \sum \frac{1}{r_i r_j} = \frac{a_2}{a_0} \]Knowing that \[ (\sum \frac{1}{r_i} )^2 \ge 2 \sum \frac{1}{r_i r_j} \]We have $a_1^2 \ge 2a_0a_2$, take the cyclic product lead to $1 \ge 2^{100}$ which is absurd
16.01.2023 19:23
Claim (well-known): If a polynomial has all real roots, then so does its derivative. Proof: Rolle's, treating roots with multiplicity $>1$ with care. Taking the $98$-th derivative of all polynomials gives $\frac{100!}{2}a_{100+k}x^2+100!a_{99+k}x+98!a_{98+k}$ has real roots, so discriminant tells us $(100a_{99+k})^2\geq 4\cdot 50\cdot 99a_{100+k}a_{98+k}$, and taking a cyclic product and $101$-st root gives $100^2\geq 200\cdot 99$, contradiction.
16.01.2023 19:38
kvedula2004 wrote: Claim (well-known): If a polynomial has all real roots, then so does its derivative. Proof: Rolle's, treating roots with multiplicity $>1$ with care. Taking the $98$-th derivative of all polynomials gives $\frac{100!}{2}a_{100+k}x^2+100!a_{99+k}x+98!a_{98+k}$ has real roots, so discriminant tells us $(100a_{99+k})^2\geq 4\cdot 50\cdot 99a_{100+k}a_{98+k}$, and taking a cyclic product and $101$-st root gives $100^2\geq 200\cdot 99$, contradiction. Had the same solution in contest ( didnt post it cuz i was sad after the contest) ngl this reminded me a lot of Putnam 2017 A3 especially how neatly everything cancels out... idk if i would get any marks since "calculus" is not in the "syllabus"
17.01.2023 20:28
I think I have a weird sol.. We use Newton's inequality to get that if \(\sum_{i=0}^n p_ix^i \) has all real roots (this is just elementary symmetric polynomial representation), then \[p_{i}^2\geq \frac{n-i+1}{n-i}\cdot\frac{i+1}{i}p_{i+1}p_{i-1}\]for all \(i\leq n-1\). Looking back at our problem, lets put \(n=100\), and \(i=1\). Note that, if we consider all possible cyclic polynomials, then note that \(p_0,p_1,p_2\) attain all values of the form \(\{a_i,a_{i+1},a_{i+2}\}\) where indices are taken modulo \(101\). So, applying Newton's inequality, we see that: \[a_{i}^2\geq a_{i+1}a_{i-1}\frac{2n}{n-1}\]Multiplying these inequalities for all \(i\), we see that \[\left(\frac{2n}{n-1}\right)^{101}\leq 1\]impossible, done. PS: Yay first post of 2023
21.01.2023 09:20
Solution from Twitch Solves ISL: Assume for contradiction. Take the reciprocal polynomial \[ Q_k(x) = a_k X^{100} + a_{k+1} X^{99} + a_{k+2} X^{98} + \dots \]which has also $101$ real roots for each $k$. Differentiate it $98$ times: \begin{align*} Q_k^{(98)}(x) &= \frac{100!}{2} a_k X^{2} + 99! a_{k+1} X + 98! a_{k+2} \\ &= 98!( 4950 a_k X^{2} + 99 a_{k+1} X + a_{k+2}). \end{align*}By Rolle's theorem this should still have $2$ real roots. Ergo, the discriminant is nonnegative: \[ (99 a_{k+1})^2 \ge 4 \cdot 4950a_k a_{k+2} \implies a_{k+1}^2 > a_k a_{k+2} \]since $99^2 < 4 \cdot 4950$. But multiplying all of these together gives a contradiction
21.01.2023 09:46
dheerstar12 wrote: Can we add all the hundred polynomials and then derive a solution Someone please confirm
21.01.2023 10:27
dheerstar12 wrote: dheerstar12 wrote: Can we add all the hundred polynomials and then derive a solution Someone please confirm I dont think so. I would be very interested to a see a solution that works, because if you add all the polynomials, you get a constant times the 101-cyclotomic polynomial and I dont think that gives anything special.
03.07.2023 11:35
Notice that if each polynomial $P_k(x)$ has all real roots, these roots are necessarily all negative, so let them be $-x_1, -x_2, \dots, -x_{100}$ for some $P_k(x)$. By AM-GM we have $$(-x_1-x_2-\cdots-x_{100})^{100} \geq 100^{100} \prod_{i=1}^{100} (-x_i) \iff \left(\frac{a_{99+k}}{a_{100+k}}\right)^{100} \geq \frac{a_k}{a_{100+k}}.$$Multiplying all of this cyclically, we see that every equation must be an equality, so in particular all the $a_i$ must be equal. However the polynomial $$P(x) =x^{100} + 100x^{99} + x^{98} + \cdots + 1$$obviously does not have $-1$ as a root, which gives the desired contradiction.
13.02.2024 06:31
Take the reciprocal polynomial\[ Q_k(x) = a_k x^{100} + a_{k+1} x^{99} + a_{k+2} x^{98} + \dots \]. Clearly, as the roots of $Q_k(x)$ are the reciprocals of that of $P_k(x)$ (the original polynomial), the former must also have all roots real. Let these roots be $r_1$ through $r_{100}$. Consider the expression $\sum_{1 \le i < j \le 100} (r_i - r_j)^2$, which is clearly nonnegative. Clearly it expands to $99\left(\sum_{i = 1}^{100} r_i^2\right) - 2 \left(\sum_{1 \le i < j \le 100} r_ir_j\right) = 99\left(\sum_{i = 1}^{100} r_i\right)^2 - 200\left(\sum_{1 \le i < j \le 100} r_ir_j\right)$, so we get $99\left(\sum_{i = 1}^{100} r_i\right)^2 \ge 200\left(\sum_{1 \le i < j \le 100} r_ir_j\right)$. From Vieta's relations, $\sum_{i = 1}^{100} r_i = -\frac{a_{k+1}}{a_k}, \sum_{1 \le i < j \le 100} r_ir_j = \frac{ a_{k+2}}{a_k}$. Subbing in, we get $99\left(\frac{a_{k+1}}{a_k}\right)^2 \ge 200\frac{ a_{k+2}}{a_k}\implies 99(a_{k+1})^2 \ge 200a_ka_{k+2}$. Cyclically multiplying over $k$ shows that this gives us $99^{100} \ge 200^{100}$, which isn't possible. $\square$
15.09.2024 21:24
The only INMO 2023 problem I am fully able to solve. Will upload it for storage coz it was lying on my computer. Solution. Observation: All roots are negative. Let the roots be $x_1,x_2,\dotsc,x_{100}$. By AM-GM and Vieta's Formula we have \begin{align*} \left(\sum_{i=1}^{100}x_i\right)^{100}=\left(\frac{100a_{99+k}}{a_{100+k}}\right)^{100}&\geq\left(\frac{a_{99+k}}{a_{100+k}}\right)^{100}\geq \prod_{i=1}^{100}x_i=\frac{a_k}{a_{100+k}}=\frac{a_{101+k}}{a_{100+k}}\\\iff \left(\frac{a_{99+k}}{a_{100+k}}\right)^{100} &\geq \frac{a_{101+k}}{a_{100+k}} \end{align*}Taking the product over all such $k\in\{0,1,2,\dots,100\}$ we see that $$\prod_{k=0}^{100}\left(\frac{a_{99+k}}{a_{100+k}}\right)^{100}\geq\quad \prod_{k=0}^{100} \frac{a_{k}}{a_{100+k}}\iff \left(\frac{a_{99}}{a_{200}}\right)^{100}=1\geq 1$$This forces $a_i=a_{i+1}\forall i\in \{k+1,\dotsc, k+99\}$. So $$P(x)=a_i(x^{100} + 100x^{99} + x^{98} + \cdots + 1)$$Now because $$\displaystyle \left(\sum_{i=1}^{100}x_i\right)=100 \quad \text{and}\quad \prod_{i=1}^{100}x_i=1 $$we have that $x_i=-1\forall i \in \{0,1,\dotsc,100\}$ $\forall i\in\{0,1,\dotsc,100\}$. But notice that $P(-1)=-98a_i\neq 0$ which gives us a contradiction.