IMO2024 Shortlisted Problems

First, observe that no polynomial is $1$-good (because $Q(X)(P(X)+Q(X))$ always has roots modulo $1$) and the polynomial $P(X)=1$ is not $2$-good (because $Q(X)(Q(X)+1)$ is always divisible by $2$).

Now, if $P$ is $d$-good with some $Q$, then $Q\cdot (P+Q)$ has no roots $\mathrm{mod}d$. Therefore, it certainly has no roots $\mathrm{mod}n$ for $d\mid n$, so $P$ must be $n$-good. Consequently, it suffices to show that all polynomials are $n$-good whenever $n$ is an odd prime, or $n=4$.

We start by handling the case $n=4$. We will construct a $Q$ such that $Q(X)$ is never divisible by $4$ and $Q(X)+P(X)$ is always odd; this will clearly show that $P$ is $4$-good. Note that any function modulo $2$ must be either constant or linear - in other words, there are $a,b\in \{0,1\}$ such that $P(X)=aX+b\mathrm{mod}2$ for all $X$. If $a=0$ then set $Q(X)=4X^2+b+1$, and if $a=1$ then set $Q(X)=X^2+b+1$; in all cases, $Q$ will satisfy the required properties.

It remains to prove that any polynomial is $p$-good, where $p$ is an odd prime. We will prove that for any function $f$ defined $\mathrm{mod}p$, there is a quadratic $Q$ with no roots $\mathrm{mod}p$ such that $Q(x)\ne f(x)\mathrm{mod}p$ for all $x$; the statement about $P$ then follows with $f$ replaced by $-P$. For the remainder of the proof, we will consider all equalities modulo $p$.

Suppose that a function $f$ not satisfying the above exists; in other words, $f$ has the property that for any quadratic $Q$ with no roots $\mathrm{mod}p$, there is some $x$ such that $Q(x)=f(x)$. Without loss of generality, we may assume that $f$ has no roots $\mathrm{mod}p$. To see why, suppose that $f(u)=0$ for some $u$, and let $g$ be the function such that $g(x)=f(x)$ for $x\ne u$ and $g(u)=1$. For any $Q$ with no roots, we know that there is some $x\ne u$ such that $P(x)=f(x)$, and so $P(x)=g(x)$ for that choice of $x$. In particular, $g$ is also not $p$-good.

Now, suppose first that there is some nonzero $t$ such that $t$ is not in the image of $f$. Then we may take $Q(X)=p{X}^2+t$; this quadratic is never equal to $f$ and is never zero. Thus, $f$ must be surjective onto the nonzero residues $\mathrm{mod}p$. There are $p$ choices for $X$ and $p-1$ nonzero residues $\mathrm{mod}p$, so there must be some $x_1\ne x_2\mathrm{mod}p$ such that $f\left(x_1\right)=f\left(x_2\right)$, and $f$ is a bijection from the set of residues $\mathrm{mod}p$ not equal to $x_2$ to the set of nonzero residues $\mathrm{mod}p$.

Now, note that we may choose any $b$ and $c$ with $b$ nonzero and replace $f(X)$ with $g(X)=f(bX+c)$; if there were some $Q$ with no roots such that $Q(x)\ne g(x)$ for all $x$, then $Q(X/b-c/b)$ would work for $f$. Choose $b$ and $c$ such that $b{x}_1+c=1$ and $b{x}_2+c=-1$; such $b$ and $c$ must exist (we may take $b=2/(x_1-x_2)$ and $c=(x_1+x_2)/(x_2-x_1)$ ). Renaming $g$ to $f$, we see that we may assume $f(1)=f(-1)$.

Let $r^{\prime }$ be a quadratic nonresidue $\mathrm{mod}p$. Choose $y\ne 0$ such that $f(y)=(1-r^{\prime })f(0)$, which must exist as the right hand side is nonzero and $1-r^{\prime }$ is not equal to $1$. Choose $r=y^2/r^{\prime }$, which is a quadratic nonresidue.

Consider $\varphi (X)=f(X)/(X^2-r)$. By definition, $\varphi (1)=\varphi (-1)$ and $\varphi (0)=\varphi (y)$, so there are no more than $p-2$ values in the image of $\varphi$. Choose some nonzero $a$ not in the image of $\varphi$, so $f(X)/(X^2-r)$ is never equal to $a$. The quadratic $Q(X)=a(X^2-r)$ is never zero and also never equal to $f(X)$, which completes the proof.

---

Alternative solution.

Given $f$ a function $\mathrm{mod}p$ such that $f$ is surjective onto the nonzero elements of $\mathbb{Z}/p\mathbb{Z}$ and $f(1)=f(-1)$, we provide an alternative approach to construct a nonzero quadratic $Q(X)$ such that $Q(X)\ne f(X)$. Let $r$ be the smallest quadratic nonresidue $\mathrm{mod}p$ (so $r-1$ is a square) and let $a$ vary over the nonzero elements $\mathrm{mod}p$; we will show that it is possible to choose $Q_a(X)=a(X^2-r)$ for some choice of $a$. Note that any quadratic of this form will be nowhere zero.

Suppose that no such $Q_a$ works. Then, for each $a$, there exists $x$ such that $a(x^2-r)=f(x)$. We may assume that $x\ne -1$, as if the equality holds for $x=-1$ then it also holds for $x=1$. However, $a(x^2-r)=f(x)$ implies $a=f(x)/(x^2-r)$, so $f(x)/(x^2-r)$ must be a surjection from $\{x\ne -1\}$ to the set of nonzero $a$, and so this is a bijection. In particular, for each $a$, there exists a unique $x_a$ such that $f(x_a)=a(x_a^2-r)$.

We now have $$\begin{array}{rl}\prod _{t\ne 0}t& =\prod _{a\ne 0}f(x_a)\\ & =\prod _{a\ne 0}a\prod _{a\ne 0}(x_a^2-r)\\ & =\prod _{a\ne 0}a\prod _{x\ne -1}(x^2-r)\end{array}$$ where the first equality follows because $f$ is surjective onto the nonzero residues $\mathrm{mod}p$, and the second equality follows from the definition of $x_a$. The two products cancel, which means that ${\prod }_{x\ne -1}(x^2-r)=1$.

However, we also get $$\prod _{x\ne -1}(x^2-r)=(-r)(1-r){\left(\prod _{x=2}^{(p-1)/2}(x^2-r)\right)}^2.$$ However, this is a contradiction as $-r(1-r)=r(r-1)$, which is not a quadratic residue (by our choice of $r$ ).

---

Alternative solution.

As in Solution 1, we will reduce to the case of $p$ being an odd prime and $f$ being a function $\mathrm{mod}p$ with no roots which is surjective onto the set of nonzero residues $\mathrm{mod}p$, although we make no assumption about the values of $x_1$ and $x_2$ with $f(x_1)=f(x_2)$.

We will again consider quadratics of the form $Q_{a,b,c}(X)=aR(bX+c)$, where $R(X)=X^2-r$ for an arbitrary fixed quadratic nonresidue $r$, $a$ and $b$ are nonzero $\mathrm{mod}p$, and $c$ is any residue $\mathrm{mod}p$.

For each fixed $b$ and $c$, there must be $n$ pairs $(a,x)$ such that $aR(bx+c)=f(x)$, because there must be exactly one value of $a$ for each $x$. If any $a$ appears in no such pair then we are done, so assume otherwise. In other words, there must be exactly one $a$ such that there are two such $x$, and for all other $a$ there is only one such $x$.

Thus, for each $(b,c)$, there is exactly one unordered pair $\{x_1,x_2\}$ such that for some $a$ we have $f(x_i)=aR(b{x}_i+c)$; in other words, there is exactly one unordered pair $\{x_1,x_2\}$ such that $f(x_1)/R(b{x}_1+c)=f(x_2)/R(b{x}_2+c)$.

Now, we show that for each unordered pair $\{x_1,x_2\}$ there must be at least one pair $(b,c)$ such that $f(x_1)/R(b{x}_1+c)=f(x_2)/R(b{x}_2+c)$. Indeed, let $t=f(x_1)/f(x_2)$. There must be some $x_1^{\prime },x_2^{\prime }$ such that $R(x_1^{\prime })/R(x_2^{\prime })=t$; this is because $R(X)$ and $tR(X)$ both take $\frac{p+1}{2}$ nonzero values $\mathrm{mod}p$, so the intersection must be nonempty by the pigeonhole principle. Choosing $b$ and $c$ such that $b{x}_1+c=x_1^{\prime }$ and $b{x}_2+c=x_2^{\prime }$ gives the claim.

Note further that if $(b,c)$ and $\{x_1,x_2\}$ satisfy the relation, then the same is true for $(-b,-c)$ and $\{x_1,x_2\}$ because $R(bx+c)=R(-bx-c)$. Since $b$ is nonzero, this means that each pair $\{x_1,x_2\}$ corresponds to at least two pairs ( $b,c$ ). However, since there are $p(p-1)$ pairs ( $b,c$ ) with $b$ nonzero and $p(p-1)/2$ unordered pairs $\{x_1,x_2\}$, each $\{x_1,x_2\}$ must correspond to exactly two pairs $(b,c)$ and $(-b,-c)$ for some $(b,c)$.

Now, since the image of $f$ has only $p-1$ elements, there must be some $x_1,x_2$ such that $f(x_1)=f(x_2)$. Choose any $b,c$ such that $b{x}_1+c=-\left(b{x}_2+c\right)$, so $R(b{x}_1+c)=R(b{x}_2+c)$ and so $f(x_1)/R(b{x}_1+c)=f(x_2)/R(b{x}_2+c)$. There is such a pair $b,c$ for any nonzero $b$, so there are at least $p-1$ such pairs, and this quantity is greater than $2$ for $p⩾5$.

Finally, for the special case that $p=3$, we observe that there must be at least one allowed value for $Q(x)$ for each $x$, so there must exist such a quadratic $Q$ by Lagrange interpolation.

Comment. We may also handle the case $p=3$ as follows. Recall that we may assume $f$ is nonzero and surjective onto $\{1,2\}\mathrm{mod}3$, so the image of $f$ must be $(1,1,2)$ or $(1,2,2)$ in some order. Without loss of generality $f(1)=f(2)$, so we either have $(f(0),f(1),f(2))=(1,2,2)$ or $(2,1,1)$. In the first case, take $Q(X)=2X^2+2$, and in the second case take $Q(X)=X^2+1$.

---

Alternative solution.

Again, we reduce to the case of $p$ being an odd prime and $f$ being a function $\mathrm{mod}p$; we will show that there is a quadratic which is nowhere zero such that $Q(x)=f(x)$ has no root. We can handle the case of $p=3$ separately as in Solution 3, so assume that $p⩾5$.

We will prove the following more general statement: let $p⩾5$ be a prime and let ${\mathcal{A}}_1,{\mathcal{A}}_2,\dots ,{\mathcal{A}}_p$ be subsets of $\mathbb{Z}/p\mathbb{Z}$ with $|{\mathcal{A}}_i|=2$ for all $i$. Then there exists a polynomial $Q\in \mathbb{Z}/p\mathbb{Z}[X]$ of degree at most $2$ such that $Q(i)\notin {\mathcal{A}}_i$ for all $i$. Indeed, applying this statement to the sets ${\mathcal{A}}_i=\{0,f(i)\}$ (and adding $p{X}^2$ if necessary) produces a quadratic $Q$ satisfying the desired property.

Choose the coefficients of $Q$ uniformly at random from $\mathbb{Z}/p\mathbb{Z}$, and let $T$ be the random variable denoting the number of $i$ for which $Q(i)\in {\mathcal{A}}_i$. Observe that for $k⩽3$, we have $$\mathbb{E}\left[\left(\genfrac{}{}{0ex}{}{T}{k}\right)\right]=2^k\left(\genfrac{}{}{0ex}{}{p}{k}\right)p^{-k}.$$ To see why, let $k⩽3$. If $\mathcal{S}\subseteq \mathbb{Z}/p\mathbb{Z}$ has size $k$ and $(a_i{)}_{i\in \mathcal{S}}$ is a $k$-tuple, the probability that $Q(i)=a_i$ on $\mathcal{S}$ is equal to $p^{-k}$; for $k=3$ this follows by Lagrange interpolation, and for $k<3$ it follows from the $k=3$ case by summing. The expectation is therefore equal to the number of $\mathcal{S}\subseteq \mathbb{Z}/p\mathbb{Z}$ of size $k$ times the probability that $Q(i)\in {\mathcal{A}}_i$ for each $i\in \mathcal{S}$, which is equal to the right hand side as each ${\mathcal{A}}_i$ has size $2$.

Now, observe that we have the identity $(t-1)(t-3)(t-4)=-12+12\left(\genfrac{}{}{0ex}{}{t}{1}\right)-10\left(\genfrac{}{}{0ex}{}{t}{2}\right)+6\left(\genfrac{}{}{0ex}{}{t}{3}\right)$, so $$\begin{array}{rl}\mathbb{E}[(T-1)(T-3)(T-4)]& =-12+12\mathbb{E}\left[\left(\genfrac{}{}{0ex}{}{T}{1}\right)\right]-10\mathbb{E}\left[\left(\genfrac{}{}{0ex}{}{T}{2}\right)\right]+6\mathbb{E}\left[\left(\genfrac{}{}{0ex}{}{T}{3}\right)\right]\\ & =-12+12\cdot 2-10\cdot 2\left(1-\frac{1}{p}\right)+6\cdot \frac{4}{3}\left(1-\frac{1}{p}\right)\left(1-\frac{2}{p}\right)\\ & =-\frac{4}{p}+\frac{16}{p^2}\end{array}$$ This is negative for $p⩾5$. Because $(t-1)(t-3)(t-4)⩾0$ for all integers $t>0$, it then follows that $T=0$ with positive probability, which implies that there must exist some $Q$ with $Q(i)\notin {\mathcal{A}}_i$ for all $i$, as desired.