2007 AMC 10A Problem 22

Question

A finite sequence of three-digit integers has the property that the tens and units digits of each term are, respectively, the hundreds and tens digits of the next term, and the tens and units digits of the last term are, respectively, the hundreds and tens digits of the first term. For example, such a sequence might begin with terms

247,

475,

and

756

and end with the term

824.

Let

S

be the sum of all the terms in the sequence. What is the largest prime number that always divides

S?

3

7

13

37

43

Answer: D

Concepts:place value divisibility

Difficulty rating: 1920

Small hint:

Because of the cyclic shifting, each digit spends equal time in the hundreds, tens, and units places

Big hint:

So

S = 111k

for some integer

k,

and

111 = 3 \cdot 37

Solution:

Each digit appears as a hundreds digit, a tens digit, and a units digit the same number of times across the sequence.

If

k

is the sum of the units digits of all terms, then

S = 111k = 3 \cdot 37 \cdot k,

so

S

is always divisible by

37.

The sequence

123,

231,

312

gives

S = 666 = 2 \cdot 3^2 \cdot 37,

which has no larger prime factor forced, so

37

is the answer.

Thus, the correct answer is D.