A Canada EGMO TST problem The Canada EGMO TST was held around a month ago across the nation, and I wish to give a talk at local math club about the problems.
I was able to solve $4$ problems, but there is one problem that I simply have no idea how to approach. However I would very much like to go through all of them during the talk.
The problem is as follows:

At least $d$ coefficients of a polynomial $P(x)$ of degree $d$ with real coefficients are equal to 1. Find the maximal value of $d$ such that $P(x)$ has $d$ real roots.

The only thought I have about this problem is that if all coefficients were $1$, then all the roots are on the unit circle in $\mathbb{C}$, and $1$ is not a root, hence it can have at most $1$ real root, namely $-1$. But I have no idea how changing one of the coefficients would affect the distribution of the roots
Any hints or thoughts are appreciated.
 A: Partial answer:
Consider $f(x) = (x-1)\cdot P(x)$, which has the form
$$f(x) = x^{d+1} + ax^{k+1}-ax^k - 1$$
for some integer $0 \le k \le d$ and real number $a$. Now apply Descartes' rule of signs to $f(x)$ and $f(-x)$ to find upper bounds for the number of positive roots and negative roots of $f$.

You can play around with this Geogebra file to see how changing $a$ affects the roots of the polynomial in the complex plane. For example, for $d=10$ and $k=4$:

As further food for thought, notice that for large $a$ the roots of $x^{d+1}+ax^{k+1}-ax^k-1$ are approximately equal to

*

*the nonzero roots of $x^{d+1}+ax^{k+1}$,

*the nonzero root of $ax^{k+1}-ax^k$, and

*the roots of $-ax^k-1$.

A: The polynomial $x^4+x^3-4x^2+x+1=(x-1)^2(x^2+3x+1)=0$ has 4 real roots. Therefore, $d\ge 4$.
We shall show that $d< 5$, completing the proof.
Let $p(x)$ be a polynomial of degree $5$ or larger and $q(x)$ be the polynomial $x^dp(x^{-1})$.
Suppose $p(x)$ be a polynomial satisfying the properties specified in the question, then so is $q(x)=x^dp(x^{-1})$.
$\textbf{Case 1:}$ Constant terms $p(0),q(0)$ are $1$.
Let the roots of $p(x)$ be $r_1,r_2,\dots,r_d$ be all real. WLOG, assume $r_1+\cdots+r_d=-1$ and $\sum\limits_{i<j} r_ir_j=1$. If not, consider $q(x)$. This is possible since $d>4$.
$$r_1^2+\cdots+r_d^2=(-1)^2+2(1)=3.$$
But by the $AM-GM$ inequality, which we can use as $r_i^2$ is positive and real, $$\frac{3}{d}=\frac{r_1^2+\cdots+r_d^2}{d}\ge \sqrt[d]{r_1^2\cdots r_d^2}=1$$ (constant terms of $p,q$ are equal to $1$.) giving a contradiction.
$\textbf{Case 2:}$ The constant term $p(0)$ (or $q(0)$) is not $1$.
The polynomial $p(x)$ is of the form $p(x)=x^d+\cdots+1+c$ for some $c\in \mathbb R$.
$\textbf{Claim:}$ If $f(x)=x^d+\cdots+1$, then $f'(x)$ has at most one real root.
Write $p(x)=x^d+\cdots+1=\frac{x^{d+1}-1}{x-1}$. Take the derivative to get $f'(x)=\frac{(d-1)x^d-dx^{d-1}+1}{(x-1)^2}$. We need to show that the numerator has at most, one root other than $1$. To do this, we can consider the derivative of $(d-1)x^d-dx^{d-1}+1$ and inspect if it is greater than or lesser than zero on the three intervals $(-\infty,0),(0,1)$ and $(1,\infty)$.
This will prove our claim.
Adding $c$ to the function $x^d+\cdots+1$ moves the graph up or down, and therefore, we can never have $3$ or more roots because between any two consecutive real roots of a polynomial, there must be a local extrema of the polynomial, but by the claim, the polynomial has at most, one local extrema.
A: This is a structure finder-structure avoider question, so we use those ideas to help us find constraints. I went into a lot more detail so that you can talk about solving this problem in a guided manner, instead of taking random stabs in the dark / being lucky. (EG It does not involve us guessing at the start that $d=4$ is the answer just because we stumbled on some polynomial that satisfies the conditions. It also shows how the constraints lead us to finding such a polynomial.)
Observation 1: To use Descarte Rule of Signs to minimize the number of positive and negative roots, we need a lot of the coefficients to be 0 in order for there to be few sign changes. Currently, $P(x)$ has a lot of non-zero coefficients, so what other polynomial can we consider?
Let the polynomial be $P(x) = 1 + x + \ldots + (1+A)x^k + \ldots + x^d$.
Observe that $(x-1) P(x) = x^{d+1} + Ax^{k+1} - Ax^k - 1 $. This is the polynomial with a lot of zero coefficients, so let's apply Descarte Rule of Signs to see what we can conclude.
Case 1: $ k \neq 0, d $. So we have 4 non-zero coefficients.
The naive direct application of Descartes tells us that

*

*Since there are 4 non-zero coefficients, there can be at most 3 sign changes irregardless of what their values are.

*Hence there are at most 3 positive roots (with multiplicity), and at most 3 negative roots (with multiplicity).

*So there are at most 6 real roots to $(x-1)P(x) = 0$.

*Thus at most 5 real roots to $P(x) = 0$.

Case 2: $ k = 0$ or $ d$
Since the number of terms is reduced, we will have fewer sign changes and hence fewer real roots. Henceforth, let's ignore this case and come back to it if needed (Spoiler: we won't need to).
Observation 2: Descarte Rule of signs tells us to hunt down those sign changes, so let's do so instead of just looking at the number of non-zero coefficients.
Let's study if all of those sign changes are possible.
In particular, since the signs of $A(-x)^{k+1} $ and $ -A(-x)^k$ are the same, which means that there are at most 2 negative roots, so there are at most 4 real roots to $P(x) = 0$. (As you will see below, all of the other sign changes are indeed possible, though I encourage you to verify this for yourself at this stage).
Observation 3: Descarte Rule of Signs tells us we want a lot of sign changes. What values of $k$ and $A$ will allow for that?
Finally, we guess that the answer is indeed $d = 4$, and it remains to find such a polynomial. Let's revisit what constants will allow us to have the desired sign changes in $(x-1)P(x)$.

*

*To get the max of 3 positive roots (but then having to exclude $x=1$), we require 1/ $ A < 0 $ and 2/ hope we don't only have 1 positive root.

*To get the max of 2 negative roots, since $A<0$, we want 1/ $k$ is even and $k \neq 0, 4$, so $k = 2$, 2/ $d+1$ is odd, which is satisfied with $d=4$, and 3/ hope we don't have 0 negative roots.

*So we should be considering $x^4 + x^3 + x^2 + x + 1 = |A| x^2$.
By AM GM, since $ x^4 + x^3 + x^2 + x + 1 \geq 5 x^2$, hence we need $|A| > 5$ for (distinct) positive real roots.

*In fact, this $|A| > 5 $ condition is sufficient. EG By considering the graph of $f(x) = x^4 + x^3 + x^2 + x + 1$ and $g(x) = |A|x^2$, showing that $ f(-\infty) > g(-\infty), f(-1) < g(-1), f(0) > g(0), f(1) < g(1), f(\infty) > g(\infty)$, so there is a real root in each of those 4 regions.

Note: If you count roots with multiplicity, then $A = -5$ suffices. This is Umesh's construction.
