2017 AMC 12A Problem 21

Problem 21 of 25HarderAlgebra Number Theory Counting & Probability

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_nx^n+a_{n-1}x^{n-1}

+\cdots+a_1x+a_0

for some

n\ge1,

all of whose coefficients

a_i

are elements of

S,

then

x

is put into

S.

When no more elements can be added to

S,

how many elements does

S

have?

Show solution

Solution

Using

10x+10,

the root

-1

enters

S.

Then

1

enters as a root of

-x^{10}-x^9-\cdots-x+10,

and

-10

enters from

x+10.

Now

x^3+x-10

has root

2,

and

x+2

gives

-2;

then

2x-10

and

2x+10

give

\pm5.

At this point

S=\{0,\pm1,\pm2,\pm5,\pm10\}.

No further integer can appear. Inductively, every nonzero member of

S

divides

10.

If a polynomial used in the rule has constant term

0,

factor out the largest possible power of

x;

any nonzero root is then a root of a polynomial whose constant term is the first nonzero original coefficient. The Rational Root Theorem shows that the root divides this coefficient, which by the inductive hypothesis divides

10.

S

has

9

elements. Thus, the correct answer is D.

Answer choices

Solution

More practice