IMO 2019 Shortlisted Problems

First, note that $0=2^1-2^1\in S$ and $2=2^2-2^1\in S$. Now, $-1\in S$, since it is a root of $2x+2$, and $1\in S$, since it is a root of $2x^2-x-1$. Also, if $n\in S$ then $-n$ is a root of $x+n$, so it suffices to prove that all positive integers must be in $S$.

Now, we claim that any positive integer $n$ has a multiple in $S$. Indeed, suppose that $n=2^{\alpha }\cdot t$ for $\alpha \in {\mathbb{Z}}_{⩾0}$ and $t$ odd. Then $t\mid 2^{\varphi (t)}-1$, so $n\mid 2^{\alpha +\varphi (t)+1}-2^{\alpha +1}$. Moreover, $2^{\alpha +\varphi (t)+1}-2^{\alpha +1}\in S$, and so $S$ contains a multiple of every positive integer $n$.

We will now prove by induction that all positive integers are in $S$. Suppose that $0,1,\dots ,n-1\in S$; furthermore, let $N$ be a multiple of $n$ in $S$. Consider the base-$n$ expansion of $N$, say $N=a_k{n}^k+a_{k-1}{n}^{k-1}+\cdots +a_{1}n+a_0$. Since $0⩽a_i<n$ for each $a_i$, we have that all the $a_i$ are in $S$. Furthermore, $a_0=0$ since $N$ is a multiple of $n$. Therefore, $a_k{n}^k+a_{k-1}{n}^{k-1}+\cdots +a_{1}n-N=0$, so $n$ is a root of a polynomial with coefficients in $S$. This tells us that $n\in S$, completing the induction.

---

Alternative solution.

As in the previous solution, we can prove that $0,1$ and $-1$ must all be in any rootiful set $S$ containing all numbers of the form $2^a-2^b$ for $a,b\in {\mathbb{Z}}_{>0}$.

We show that, in fact, every integer $k$ with $|k|>2$ can be expressed as a root of a polynomial whose coefficients are of the form $2^a-2^b$. Observe that it suffices to consider the case where $k$ is positive, as if $k$ is a root of $a_n{x}^n+\cdots +a_{1}x+a_0=0$, then $-k$ is a root of $(-1{)}^n{a}_n{x}^n+\cdots -a_{1}x+a_0=0$.

Note that $$\left(2^{a_n}-2^{b_n}\right)k^n+\cdots +\left(2^{a_0}-2^{b_0}\right)=0$$ is equivalent to $$2^{a_n}{k}^n+\cdots +2^{a_0}=2^{b_n}{k}^n+\cdots +2^{b_0}.$$ Hence our aim is to show that two numbers of the form $2^{a_n}{k}^n+\cdots +2^{a_0}$ are equal, for a fixed value of $n$. We consider such polynomials where every term $2^{a_i}{k}^i$ is at most $2k^n$; in other words, where $2⩽2^{a_i}⩽2k^{n-i}$, or, equivalently, $1⩽a_i⩽1+(n-i){\log }_{2}k$. Therefore, there must be $1+\lfloor (n-i){\log }_{2}k\rfloor$ possible choices for $a_i$ satisfying these constraints.

The number of possible polynomials is then $$\prod _{i=0}^n\left(1+\lfloor (n-i){\log }_{2}k\rfloor \right)⩾\prod _{i=0}^{n-1}(n-i){\log }_{2}k=n!{\left({\log }_{2}k\right)}^n$$ where the inequality holds as $1+\lfloor x\rfloor ⩾x$.

As there are $(n+1)$ such terms in the polynomial, each at most $2k^n$, such a polynomial must have value at most $2k^n(n+1)$. However, for large $n$, we have $n!{\left({\log }_{2}k\right)}^n>2k^n(n+1)$. Therefore there are more polynomials than possible values, so some two must be equal, as required.