2007 AMC 10A Problem 22

P21-25~4 minPrint

Bases & Digits Primes Test small/specific values or special cases to find or verify the answer Exploit symmetry to reduce work or pair up objects

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 the 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 factor that always divides $S$ ?

Show solution without answering

Key insight

The digits wrap around, so each digit appears once as a hundreds, once as a tens and once as a ones digit. The sum is 111 times the digit total.

Solution

Try a short example first: $123, 231, 312$ . Each term starts with the last two digits of the one before, and $312$ leads back to $123$ . So this sequence follows the rule.

Look at the columns.

	hundreds	tens	ones
$123$	1	2	3
$231$	2	3	1
$312$	3	1	2

The hundreds column holds $1, 2, 3$ , and so do the tens and the ones columns, just shifted.
2. Why this always happens. Think of the digits written around a circle. Each term reads three digits in a row. As you move around, each digit is first a ones digit, then a tens digit in the next term, then a hundreds digit in the term after that. Because the list wraps around, this works even at the end.
3. So the sum splits nicely. Let $T$ be the total of the digits around the circle. The hundreds digits add to $T$ , the tens digits add to $T$ , and the ones digits add to $T$ . So
$S = 100T + 10T + T = 111\,T.$
4. Factor $111$ . $111 = 3 \times 37$ . So $37$ always divides $S$ .
5. Nothing bigger always works. For $123, 231, 312$ the sum is $666 = 2 \times 3 \times 3 \times 37$ . The only choice bigger than $37$ is $43$ , and $43$ does not divide $666$ .

The answer is $\boxed{\textbf{(D)}\ 37}$ .

Why this works

The wrap-around rule means every digit gets used once in each place, so the sum is always $111$ times something. "Always divides" questions have two halves: show the number works for every sequence, then give one example where a bigger number fails. It helps to know $111 = 3 \times 37$ on sight.

Alternative approach

Finish the example from the problem into a full loop: $247, 475, 756, 568, 682, 824$ . The sum is $3552 = 111 \times 32$ . Among the choices, only $3$ and $37$ divide it, and $37$ is bigger. The column argument above then confirms that $37$ works every time.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Picture the terms as a ring of digits $d_1, d_2, \ldots, d_k$ read cyclically: the $i$ -th term is $d_i d_{i+1} d_{i+2}$ (indices wrapping around). Each digit $d_i$ serves as the hundreds digit of one term, the tens digit of the previous term, and the units digit of the one before that.

So if $T = d_1 + d_2 + \cdots + d_k$ is the total of the ring's digits, then
$S = 100T + 10T + T = 111\,T = 3 \cdot 37 \cdot T.$
Thus $37$ always divides $S$ .

No larger prime is guaranteed: the sequence $123, 231, 312$ is valid and sums to $666 = 2 \cdot 3^2 \cdot 37$ , which is not divisible by $43$ (or by any prime above $37$ ).

The answer is $\boxed{\textbf{(D)}\ 37}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 8: Base Numbers
Introduction to Number Theory, Chapter 2: Primes and Composites
Introduction to Algebra, Chapter 22: Special Manipulations (§22.3)
Introduction to Number Theory, Chapter 9: Base Number Arithmetic