0
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Note that $10x + 10 = 0$ allows $-1$ to be added to $S $. $\endgroup$ – hardmath Oct 8 '17 at 13:02
  • 1
    $\begingroup$ @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$. $\endgroup$ – quasi Oct 8 '17 at 13:03
  • $\begingroup$ Also, $n$ is not tied to the size of $S$. As $S$ grows, you can still use any positive integer $n$. $\endgroup$ – quasi Oct 8 '17 at 13:10
  • $\begingroup$ I edited in the $a_n \ne 0$ requirement, as one way to bar the zero polynomial. $\endgroup$ – quasi Oct 8 '17 at 14:48
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Hagen von Eitzen Oct 8 '17 at 15:21
  • $\begingroup$ Good question! I'll try it. $\endgroup$ – quasi Oct 8 '17 at 16:01
  • $\begingroup$ @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$. $\endgroup$ – quasi Oct 8 '17 at 16:50
  • $\begingroup$ It's not quite as simple as I thought. My claim above is not true. For example, $S$ is full for $n=95$. $\endgroup$ – quasi Oct 8 '17 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.