# polynomials$\,-\,$an AMC contest problem

A set $S$ is constructed as follows. To begin, $S = \{0,10\}$. Repeatedly, as long as possible, if $x$ is an integer root of some polynomial $a_{n}x^n + a_{n-1}x^{n-1} + ... + a_{1}x + a_0$, for some $n\geq{1}$, all of whose coefficients $a_i$ are elements of $S$, and where $a_n \ne 0$, then $x$ is put into $S$. When no more elements can be added to $S$, how many elements does $S$ have?

This is another AMC question... and the problem is, I don't quite understand it. So when $S = \{0,10\}$, what does the polynomial look like? Is it $0x^2+10x$ because there are two numbers in the set? But then how would I account for $a_0$? I'm really confused, and any help would really be appreciated!

• Note that $10x + 10 = 0$ allows $-1$ to be added to $S$. – hardmath Oct 8 '17 at 13:02
• @Helena: Are you sure you copied the question correctly? My guess is the question requires $a_n \ne 0$. Otherwise, using the zero polynomial, every integer would qualify as an element of $S$. – quasi Oct 8 '17 at 13:03
• Also, $n$ is not tied to the size of $S$. As $S$ grows, you can still use any positive integer $n$. – quasi Oct 8 '17 at 13:10
• I edited in the $a_n \ne 0$ requirement, as one way to bar the zero polynomial. – quasi Oct 8 '17 at 14:48

With $S = \{0,10\}$:

$\qquad$The equation $10x + 10 = 0$ has root $x = -1$.

With $S = \{0,-1,10\}$:

$\qquad$The equation $-x^{10} - x^9 - x^8 - \cdots - x + 10 = 0$ has root $x = 1$.

With $S = \{0,\pm 1,10\}$:

$\qquad$The equation $x + 10 = 0$ has root $x = -10$

$\qquad$The equation $-x^3 - x + 10 = 0$ has root $x = 2$.

$\qquad$The equation $x^3 + x + 10 = 0$ has root $x = -2$.

With $S = \{0,\pm 1, \pm 2, \pm 10\}$:

$\qquad$The equation $2x -10 = 0$ has root $x = 5$.

$\qquad$The equation $2x + 10 = 0$ has root $x = -5$.

So now $S = \{0,\pm 1,\pm2, \pm 5, \pm 10\}$.

Claim no other integers can be added to $S$.

Suppose instead there is a nonzero polynomial with coefficients in $S$ which has an integer root not in $S$.

Of all such polynomials, let $$f(x) = a_nx^n + \cdots + a_0$$ be one for which $\deg(f) = n$ is least.

Let $r$ be an integer root of $f$, with $r \notin S$.

Any integer root of $f$ would have to divide $a_0$.

But the integer factors of the nonzero elements of $S$ are already in $S$.

Hence, since $r \notin S$, it follows that $a_0=0$.

Let $g(x) = f(x)/x$. Then

• $g$ is a nonzero polynomial with coefficients in $S$.$\\[4pt]$
• $g(r) = 0$.$\\[4pt]$
• $\deg(g) = n-1$

contrary to the least degree property of $f$.

Therefore $S = \{0,\pm 1,\pm2, \pm 5, \pm 10\}$ is final, and has $9$ elements.

• In general, staring with $S=\{0,n\}$ we end up with at most the divisors of $n$ and $0$. Is there an $n$ where the final $S$ is (easily seen to be) smaller? – Hagen von Eitzen Oct 8 '17 at 15:21
• Good question! I'll try it. – quasi Oct 8 '17 at 16:01
• @Hagen von Eitzen: I have a tentative proof (not written out, so it could be wrong) of the following claim: The final $S$ is full if and only if the number of distinct prime factors of $n$ which exceed $3$ is at most $1$. Thus, the smallest positive integer value of $n$ for which $S$ is not full is $n=35$. – quasi Oct 8 '17 at 16:50
• It's not quite as simple as I thought. My claim above is not true. For example, $S$ is full for $n=95$. – quasi Oct 8 '17 at 18:20