2014 AMC 10A Problem 20

P16-20~3 minPrint

Bases & Digits Compute small cases, spot the pattern, generalize

The product $(8)(888\dots8)$ , where the second factor has $k$ digits, is an integer whose digits have a sum of $1000$ . What is $k$ ?

Show solution without answering

Key insight

Work out 8 times 88, 888, 8888. The answer is always a 7, then a run of ones, then 04, so the digit sum is k + 9.

Solution

The number is far too long to write out, so work out small cases and look for a pattern.

Multiply:

$k$	product	digit sum
$2$	$8 \cdot 88 = 704$	$11$
$3$	$8 \cdot 888 = 7104$	$12$
$4$	$8 \cdot 8888 = 71104$	$13$
$5$	$8 \cdot 88888 = 711104$	$14$

2. The pattern. Each product is a $7$ , then some $1$ s, then $04$ . Each time $k$ goes up by one, one more $1$ appears. With $k$ eights there are $k - 2$ ones.
3. Why it keeps going. Adding one more $8$ to the long number is the same as multiplying it by $10$ and adding $8$ . So the new product is the old product times $10$ , plus $8 \cdot 8 = 64$ . For example, $7104 \cdot 10 + 64 = 71040 + 64 = 71104$ . The ending $040$ becomes $104$ : one new $1$ appears and the $04$ at the end stays.
4. Digit sum. $7$ , plus $k - 2$ ones, plus $0 + 4$ :
$7 + (k - 2) + 4 = k + 9.$
Check with $k = 3$ : $3 + 9 = 12$ . Matches the table.
5. Solve. $k + 9 = 1000$ , so $k = 991$ .

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

Why this works

A number made of one repeated digit, multiplied by a single digit, has a very regular answer: every column does the same multiplication, and after the first couple of columns the carries settle into the same value each time. Three or four small cases show the pattern, and the step "times $10$ , plus $64$ " explains why it never breaks.

Alternative approach

Notice that $8 \cdot 88\ldots8 = 64 \cdot 11\ldots1$ , with $k$ ones. Multiply $64$ by a long string of ones column by column. Each middle column adds $6 + 4 = 10$ plus a carry of $1$ , which gives $11$ : write $1$ , carry $1$ . The last column gives $4$ , the next gives $6 + 4 = 10$ (write $0$ , carry $1$ ), and the front gives $6 + 1 = 7$ . So the product is $7$ , then $k - 2$ ones, then $04$ , the same pattern.

Concise solution

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

Compute the first few products:
$8 \cdot 8 = 64,\quad 8 \cdot 88 = 704,\quad 8 \cdot 888 = 7104,\quad 8 \cdot 8888 = 71104,\quad 8 \cdot 88888 = 711104.$

For $k \ge 2$ the product is a $7$ , followed by $k - 2$ ones, followed by $04$ . To see why the pattern continues, let $P_k = 8 \cdot \underbrace{88\dots8}_{k}$ . Since $\underbrace{88\dots8}_{k} = 10 \cdot \underbrace{88\dots8}_{k-1} + 8$ ,
$P_k = 10 P_{k-1} + 64.$
Appending a $0$ to $71\dots104$ gives $71\dots1040$ , and adding $64$ turns the final $040$ into $104$ : one more $1$ appears and the ending $04$ is preserved.

The digit sum of $P_k$ is therefore
$7 + (k - 2)\cdot 1 + 0 + 4 = k + 9.$
Setting $k + 9 = 1000$ gives $k = 991$ .

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

Review in the AoPS books

Introduction to Number Theory, Chapter 8: Base Numbers
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.1)
Introduction to Number Theory, Chapter 9: Base Number Arithmetic
Introduction to Number Theory, Chapter 12: Introduction to Modular Arithmetic (§12.6)