, 2019

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 $2 x+2$, and $1 \in S$, since it is a root of $2 x^{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}_{\geqslant 0}$ and $t$ odd. Then $t \mid 2^{\phi(t)}-1$, so $n \mid 2^{\alpha+\phi(t)+1}-2^{\alpha+1}$. Moreover, $2^{\alpha+\phi(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, \ldots, 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 \leqslant 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.

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 $2 k^{n}$; in other words, where $2 \leqslant 2^{a_{i}} \leqslant 2 k^{n-i}$, or, equivalently, $1 \leqslant a_{i} \leqslant 1+(n-i) \log_{2} k$. Therefore, there must be $1+\left\lfloor(n-i) \log_{2} k\right\rfloor$ possible choices for $a_{i}$ satisfying these constraints.

The number of possible polynomials is then
$$\prod_{i=0}^{n}\left(1+\left\lfloor(n-i) \log_{2} k\right\rfloor\right) \geqslant \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 \geqslant x$.

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