2004 AIME I Problems/Problem 15

Problem

For all positive integers $x$ , let $f(x)=\begin{cases}1 & \text{if }x = 1\\ \frac x{10} & \text{if }x\text{ is divisible by 10}\\ x+1 & \text{otherwise}\end{cases}$ and define a sequence as follows: $x_1=x$ and $x_{n+1}=f(x_n)$ for all positive integers $n$ . Let $d(x)$ be the smallest $n$ such that $x_n=1$ . (For example, $d(100)=3$ and $d(87)=7$ .) Let $m$ be the number of positive integers $x$ such that $d(x)=20$ . Find the sum of the distinct prime factors of $m$ .

Solution

We backcount the number of ways. Namely, we start at $x_{20} = 1$ , which can only be reached if $x_{19} = 10$ , and then we perform $18$ operations that either consist of $A: (-1)$ or $B: (\times 10)$ . We represent these operations in a string format, starting with the operation that sends $f(x_{18}) = x_{19}$ and so forth downwards. There are $2^9$ ways to pick the first $9$ operations; however, not all $9$ of them may be $A: (-1)$ otherwise we return back to $x_{10} = 1$ , contradicting our assumption that $20$ was the smallest value of $n$ . Using complementary counting, we see that there are only $2^9 - 1$ ways.

Since we performed the operation $B: (\times 10)$ at least once in the first $9$ operations, it follows that $x_{10} \ge 20$ , so that we no longer have to worry about reaching $1$ again. Thus the remaining $9$ operations can be picked in $2^9$ ways, with a total of $2^9(2^9 - 1) = 2^{18} - 2^9$ strings.

However, we must also account for a sequence of $10$ or more $A: (-1)$ s in a row, because that implies that at least one of those numbers was divisible by $10$ , yet the $\frac{x}{10}$ was never used, contradiction. We must use complementary counting again by determining the number of strings of $A,B$ s of length $18$ such that there are $10$ $A$ s in a row. The first ten are not included since we already accounted for that scenario above, so our string of $10$ $A$ s must be preceded by a $B$ . There are no other restrictions on the remaining seven characters. Letting $\square$ to denote either of the functions, and $^{[k]}$ to indicate that the character appears $k$ times in a row, then our bad strings can take the forms: $\begin{align*} &\underbrace{BA^{[10]}}\square \square \square \square \square \square \square \square \\ &\square \underbrace{BA^{[10]}}\square \square \square \square \square \square \square \\ &\qquad \quad \cdots \quad \cdots \\ &\square \square \square \square \square \square \square \underbrace{BA^{[10]}} \square \\ &\square \square \square \square \square \square \square \square \underbrace{BA^{[10]}} \\ \end{align*}$

There are $2^7$ ways to select the operations for the $7$ $\square$ s, and $8$ places to place our $BA^{[10]}$ block. Thus, our answer is $2^{18} - 2^9 - 8 \cdot 2^7 = 2^9 \times 509$ , and the answer is $\boxed{511}$ .

2004 AIME I (Problems • Answer Key • Resources)
Preceded by Problem 14	Followed by Last Question
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search

2004 AIME I Problems/Problem 15

Problem

Solution

See also