Difference between revisions of "2004 AIME I Problems/Problem 15"

Revision as of 22:34, 24 February 2016

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

Solution 1

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}$ .

Solution 2

We approach the problem by recursion. We partition the positive integers into the sets $\mathcal{A}_{n,k}=\{x\in\mathbb{Z}^+\,:\, d(x)=n\text{ and } x\equiv k\pmod{10}\}.$ First, we note that $\mathcal{A}_{1,1}=\{1\}$ , so by the disjointness of the $\mathcal{A}_{n,k}$ 's, we know that $1$ is not in any of the other sets. Also, we note that $\mathcal{A}_{1,k}=\emptyset$ for $k=0,2,3,4,5,6,7,8,9$ .

We claim that if $2\le k\le 9$ and $n\ge2$ , then $|\mathcal{A}_{n,k}|=|\mathcal{A}_{n-1,k+1}|$ . To prove this, we show that $f$ (the given function) maps $\mathcal{A}_{n,k}$ bijectively onto $\mathcal{A}_{n-1,k+1}$ . If $x\in \mathcal{A}_{n,k}$ , then $x\equiv k\pmod{10}$ , and $x\ne 1$ , so $f(x)=x+1\equiv k+1\pmod{10}$ . Also, $f^{(n)}(x)=1$ , where $n$ is the smallest positive integer for which this is true. Therefore, $f^{{n-1}}(f(x))=1$ , where $n-1$ is the smallest integer for which this is true. Thus $f(x)\in\mathcal{A}_{n-1,k+1}$ . Also, since $f(x)=x+1$ on this set, we see that $f(x)=f(y)$ implies that $x=y$ . Hence $f$ is an injection. If $y\in\mathcal{A}_{n-1,k+1}$ , then $y-1\equiv k\pmod{10}$ , where $2\le k\le 9$ , so we know that $f(y-1)=y$ , and $y-1\in \mathcal{A}_{n,k}$ . Therefore, $f$ is a surjection, so it must be a bijection. Therefore, if $2\le k\le 9$ and $n\ge2$ , then $|\mathcal{A}_{n,k}|=|\mathcal{A}_{n-1,k+1}|$ .

We also claim that if $k=1$ , $n\ge 2$ and $n\ne 11$ , then $|\mathcal{A}_{n,k}|=|\mathcal{A}_{n-1,k+1}|$ . The proof is the same as in the previous paragraph, though some additional clarification is needed to prove that $f$ is a surjection. If $y\in\mathcal{A}_{n-1,k+1}$ , or rather $y-1\equiv k\equiv 1\pmod{10}$ , then if $y=2$ , we see that $y-1=1$ , and then $f(y-1)=1$ , not $y$ as in the prior argument. However, this does not happen if $n\ne 11$ . It is easy to check that $2\in\mathcal{A}_{10,2}$ . Therefore, the only time that the above argument could fail is if $n-1=10$ and $k+1=2$ . But in every other case, $|\mathcal{A}_{n,k}|=|\mathcal{A}_{n-1,k+1}|$ .

Next, we claim that if $n\ge 3$ , then $|\mathcal{A}_{n,0}|=\Big|\bigcup_{k=0}^9\mathcal{A}_{n-1,k}\Big|$ If $x\in\mathcal{A}_{n,0}$ , then $f(x)=\tfrac{x}{10}$ , which is clearly an injective map. Also, $f^{(n)}(x)=1$ , where $n$ is the smallest positive integer for which this is true. Therefore, $f^{{n-1}}(f(x))=1$ , where $n-1$ is the smallest integer for which this is true. Thus $f(x)\in\mathcal{A}_{n-1,k}$ for some $k$ . Conversely, if $y\in \mathcal{A}_{n-1,k}$ , then $f(10y)=y$ , so $d(10y)=n$ , so $10y\in\mathcal{n,0}$ .

Based on these bijections, if we let $A_{n,k}=|\mathcal{A}_{n,k}|$ , then $\begin{align*} A_{n,0}&=\sum_{k=0}^{9} A_{n-1,k}\\ A_{n,1}&=A_{n-1,2}\qquad\text{if }n\ne 11\\ A_{n,2}&=A_{n-1,3}\\ A_{n,3}&=A_{n-1,4}\\ &\vdots\\ A_{n,8}&=A_{n-1,9}\\ A_{n,9}&=A_{n-1,0}. \end{align*}$ Let $S_n=\sum_{k=0}^9 A_{n,k}$ . Then by adding the above equations, we find that $S_n=2S_{n-1}-A_{n-1,1}.$ Now by using the above relations repeatedly, we find $A_{n-1,1}=A_{n-2,2}=A_{n-3,3}=\cdots=A_{n-9,9}=A_{n-10,0}=S_{n-11}.$ Therefore, $S_n=2S_{n-1}-S_{n-11}$ for $n\ge 12$ . For smaller values, it is easy to use the relations to compute that the terms are powers of $2$ , although we note that $A_{10,1}=0$ because of the failure of the above argument. $\begin{array}{c|cccccccccc|c} n&A_{n,1}&A_{n,2}&A_{n,3}&A_{n,4}&A_{n,5}&A_{n,6}&A_{n,7}&A_{n,8}&A_{n,9}&A_{n,0}&S_{n}\\\hline 1&1&0&0&0&0&0&0&0&0&0&1\\ 2&0&0&0&0&0&0&0&0&0&1&1\\ 3&0&0&0&0&0&0&0&0&1&1&2\\ 4&0&0&0&0&0&0&0&1&1&2&4\\ 5&0&0&0&0&0&0&1&1&2&4&8\\ 6&0&0&0&0&0&1&1&2&4&8&16\\ 7&0&0&0&0&1&1&2&4&8&16&32\\ 8&0&0&0&1&1&2&4&8&16&32&64\\ 9&0&0&1&1&2&4&8&16&32&64&128\\ 10&0&1&1&2&4&8&16&32&64&128&256\\ 11&\boxed{0}&1&2&4&8&16&32&64&128&256&511\\ 12&1&2&4&8&16&32&64&128&256&511&1022\\ \end{array}$ After this, we can simply use the recurrence relation for $S_n$ , finding $\begin{array}{c|l} n&S_n\\\hline 1&1\\ 2&1\\ 3&2^1\\ 4&2^2\\ 5&2^3\\ 6&2^4\\ 7&2^5\\ 8&2^6\\ 9&2^7\\ 10&2^8\\ 11&2^9-1\\ 12&2^{10}-2\\ 13&2^{11}-1\cdot 5\\ 14&2^{12}-2\cdot 6\\ 15&2^{13}-4\cdot 7\\ 16&2^{14}-8\cdot 8\\ 17&2^{15}-16\cdot 9\\ 18&2^{16}-32\cdot 10\\ 19&2^{17}-64\cdot 11\\ 20&2^{18}-128\cdot 12. \end{array}$ Therefore, there are $2^{18}- 2^9\cdot 3$ positive integers $x$ with $d(x)=20$ . This factors as $2^9(2^{9}-3)=2^9(509)$ , where $509$ is prime. Thus 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