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

m (Solution 2)
 
(19 intermediate revisions by 7 users not shown)
Line 7: Line 7:
  
 
== Solution ==
 
== Solution ==
 +
=== Solution 1 ===
 
We backcount the number of ways. Namely, we start at <math>x_{20} = 1</math>, which can only be reached if <math>x_{19} = 10</math>, and then we perform <math>18</math> operations that either consist of <math>A: (-1)</math> or <math>B: (\times 10)</math>. We represent these operations in a string format, starting with the operation that sends <math>f(x_{18}) = x_{19}</math> and so forth downwards. There are <math>2^9</math> ways to pick the first <math>9</math> operations; however, not all <math>9</math> of them may be <math>A: (-1)</math> otherwise we return back to <math>x_{10} = 1</math>, contradicting our assumption that <math>20</math> was the smallest value of <math>n</math>. Using [[complementary counting]], we see that there are only <math>2^9 - 1</math> ways.
 
We backcount the number of ways. Namely, we start at <math>x_{20} = 1</math>, which can only be reached if <math>x_{19} = 10</math>, and then we perform <math>18</math> operations that either consist of <math>A: (-1)</math> or <math>B: (\times 10)</math>. We represent these operations in a string format, starting with the operation that sends <math>f(x_{18}) = x_{19}</math> and so forth downwards. There are <math>2^9</math> ways to pick the first <math>9</math> operations; however, not all <math>9</math> of them may be <math>A: (-1)</math> otherwise we return back to <math>x_{10} = 1</math>, contradicting our assumption that <math>20</math> was the smallest value of <math>n</math>. Using [[complementary counting]], we see that there are only <math>2^9 - 1</math> ways.
  
Since we performed the operation <math>B: (\times 10)</math> at least once in the first <math>9</math> operations, it follows that <math>x_{10} \ge 20</math>, so that we no longer have to worry about reaching <math>1</math> again. Thus the remaining <math>9</math> operations can be picked in <math>2^9</math> ways, with a total of <math>2^9(2^9 - 1) = 2^{18} - 2^9</math> strings.  
+
Since we performed the operation <math>B: (\times 10)</math> at least once in the first <math>9</math> operations, it follows that <math>x_{10} \ge 20</math>, so that we no longer have to worry about reaching <math>1</math> again.  
  
However, we must also account for a sequence of <math>10</math> or more <math>A: (-1)</math>s in a row, because that implies that at least one of those numbers was divisible by <math>10</math>, yet the <math>\frac{x}{10}</math> was never used, contradiction. We must use complementary counting again by determining the number of strings of <math>A,B</math>s of length <math>18</math> such that there are <math>10</math> <math>A</math>s in a row. The first ten are not included since we already accounted for that scenario above, so our string of <math>10</math> <math>A</math>s must be preceded by a <math>B</math>. There are no other restrictions on the remaining seven characters. Letting <math>\square</math> to denote either of the functions, and <math>^{[k]}</math> to indicate that the character appears <math>k</math> times in a row, then our bad strings can take the forms:
+
However, we must also account for a sequence of <math>10</math> or more <math>A: (-1)</math>s in a row, because that implies that at least one of those numbers was divisible by <math>10</math>, yet the <math>\frac{x}{10}</math> was never used, contradiction. We must use complementary counting again by determining the number of strings of <math>A,B</math>s of length <math>18</math> such that there are <math>10</math> <math>A</math>s in a row. The first ten are not included since we already accounted for that scenario above, so our string of <math>10</math> <math>A</math>s must be preceded by a <math>B</math>. There are no other restrictions on the remaining seven characters. Letting <math>\square</math> to denote either of the functions, and <math>^{[k]}</math> to indicate that the character appears <math>k</math> times in a row, our bad strings can take the forms:
<center><math>\begin{align*}
+
<cmath>\begin{align*}
&\underbrace{BA^{[10]}}\square \square \square \square \square \square \square \square \\
+
&\underbrace{BA^{[10]}}\square \square \square \square \square \square \square\\
&\square \underbrace{BA^{[10]}}\square \square \square \square \square \square \square \\
+
&\square \underbrace{BA^{[10]}}\square \square \square \square \square \square \\
 
&\qquad \quad \cdots \quad \cdots \\
 
&\qquad \quad \cdots \quad \cdots \\
&\square \square \square \square \square \square \square \underbrace{BA^{[10]}} \square \\
+
&\square \square \square \square \square \square \underbrace{BA^{[10]}} \square \\
&\square \square \square \square \square \square \square \square \underbrace{BA^{[10]}} \\
+
&\square \square \square \square \square \square \square \underbrace{BA^{[10]}} \\
\end{align*}</math></center>
+
\end{align*}</cmath>
  
There are <math>2^7</math> ways to select the operations for the <math>7</math> <math>\square</math>s, and <math>8</math> places to place our <math>BA^{[10]}</math> block. Thus, our answer is <math>2^{18} - 2^9 - 8 \cdot 2^7 = 2^9 \times 509</math>, and the answer is <math>\boxed{511}</math>.
+
There are <math>2^7</math> ways to select the operations for the <math>7</math> <math>\square</math>s, and <math>8</math> places to place our <math>BA^{[10]}</math> block. Thus, our answer is <math>2^9(2^9-1)-8\cdot 2^7 = 2^{18} - 2^9 - 8 \cdot 2^7 = 2^9 \times 509</math>, and the answer is <math>\boxed{511}</math>.
 +
 
 +
'''Note:''' This solution is quick and most similar to the official solution; however, neither this nor the official solution prove that the final results of these inverted operations are all distinct. A more sophisticated argument, such as the one below, is needed to do so.
 +
 
 +
=== Solution 2 ===
 +
We approach the problem by [[recursion]]. We [[partition]] the positive integers into the sets
 +
<cmath>\mathcal{A}_{n,k}=\{x\in\mathbb{Z}^+\,:\, d(x)=n\text{ and } x\equiv k\pmod{10}\}.</cmath>
 +
First, we note that <math>\mathcal{A}_{1,1}=\{1\}</math>, so by the [[disjoint]]ness of the <math>\mathcal{A}_{n,k}</math>'s, we know that <math>1</math> is not in any of the other sets. Also, we note that <math>\mathcal{A}_{1,k}=\emptyset</math> for <math>k=0,2,3,4,5,6,7,8,9</math>.
 +
 
 +
We claim that if <math>2\le k\le 9</math> and <math>n\ge2</math>, then <math>|\mathcal{A}_{n,k}|=|\mathcal{A}_{n-1,k+1}|</math>. To prove this, we show that <math>f</math> (the given function) maps <math>\mathcal{A}_{n,k}</math> bijectively onto <math>\mathcal{A}_{n-1,k+1}</math>. If <math>x\in \mathcal{A}_{n,k}</math>, then <math>x\equiv k\pmod{10}</math>, and <math>x\ne 1</math>, so <math>f(x)=x+1\equiv k+1\pmod{10}</math>. Also, <math>f^{(n)}(x)=1</math>, where <math>n</math> is the smallest positive integer for which this is true. Therefore, <math>f^{{n-1}}(f(x))=1</math>, where <math>n-1</math> is the smallest integer for which this is true. Thus <math>f(x)\in\mathcal{A}_{n-1,k+1}</math>. Also, since <math>f(x)=x+1</math> on this set, we see that <math>f(x)=f(y)</math> implies that <math>x=y</math>. Hence <math>f</math> is an [[injection]]. If <math>y\in\mathcal{A}_{n-1,k+1}</math>, then <math>y-1\equiv k\pmod{10}</math>, where <math>2\le k\le 9</math>, so we know that <math>f(y-1)=y</math>, and <math>y-1\in \mathcal{A}_{n,k}</math>. Therefore, <math>f</math> is a [[surjection]], so it must be a [[bijection]]. Therefore,  if <math>2\le k\le 9</math> and <math>n\ge2</math>, then <math>|\mathcal{A}_{n,k}|=|\mathcal{A}_{n-1,k+1}|</math>.
 +
 
 +
We also claim that if <math>k=1</math>, <math>n\ge 2</math> and <math>n\ne 11</math>, then  <math>|\mathcal{A}_{n,k}|=|\mathcal{A}_{n-1,k+1}|</math>. The proof is the same as in the previous paragraph, though some additional clarification is needed to prove that <math>f</math> is a surjection. If <math>y\in\mathcal{A}_{n-1,k+1}</math>, or rather <math>y-1\equiv k\equiv 1\pmod{10}</math>, then if <math>y=2</math>, we see that <math>y-1=1</math>, and then <math>f(y-1)=1</math>, not <math>y</math> as in the prior argument. However, this does not happen if <math>n\ne 11</math>. It is easy to check that <math>2\in\mathcal{A}_{10,2}</math>. Therefore, the only time that the above argument could fail is if <math>n-1=10</math> and <math>k+1=2</math>. But in every other case, <math>|\mathcal{A}_{n,k}|=|\mathcal{A}_{n-1,k+1}|</math>.
 +
 
 +
Next, we claim that if <math>n\ge 3</math>, then
 +
<cmath>|\mathcal{A}_{n,0}|=\Big|\bigcup_{k=0}^9\mathcal{A}_{n-1,k}\Big|</cmath>
 +
If <math>x\in\mathcal{A}_{n,0}</math>, then <math>f(x)=\tfrac{x}{10}</math>, which is clearly an injective map.  Also, <math>f^{(n)}(x)=1</math>, where <math>n</math> is the smallest positive integer for which this is true. Therefore, <math>f^{{n-1}}(f(x))=1</math>, where <math>n-1</math> is the smallest integer for which this is true. Thus <math>f(x)\in\mathcal{A}_{n-1,k}</math> for some <math>k</math>. Conversely, if <math>y\in \mathcal{A}_{n-1,k}</math>, then <math>f(10y)=y</math>, so <math>d(10y)=n</math>, so <math>10y\in\mathcal{A}_{n,0}</math>.
 +
 
 +
Based on these bijections, if we let <math>A_{n,k}=|\mathcal{A}_{n,k}|</math>, then
 +
<cmath>\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*}</cmath>
 +
Let <math>S_n=\sum_{k=0}^9 A_{n,k}</math>. Then by adding the above equations (valid if <math>n\ne 11</math>), we find that
 +
<cmath>S_n=2S_{n-1}-A_{n-1,1}.</cmath>
 +
Now by using the above relations repeatedly, we find
 +
<cmath>A_{n-1,1}=A_{n-2,2}=A_{n-3,3}=\cdots=A_{n-9,9}=A_{n-10,0}=S_{n-11}.</cmath>
 +
The first relation will only be valid if <math>n\ne 12</math>. Therefore, <math>S_n=2S_{n-1}-S_{n-11}</math> for <math>n\ge 13</math>. For smaller values, it is easy to use the relations to compute that the terms are powers of <math>2</math>, although we note that <math>A_{11,1}=0</math> because of the failure of the above argument.
 +
<cmath>\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}</cmath>
 +
After this, we can simply use the recurrence relation for <math>S_n</math>, finding
 +
<cmath>\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}</cmath>
 +
Therefore, there are <math>2^{18}- 2^9\cdot 3</math> positive integers <math>x</math> with <math>d(x)=20</math>. This factors as <math>2^9(2^{9}-3)=2^9(509)</math>, where <math>509</math> is prime. Thus the answer is <math>\boxed{511}</math>.
  
 
== See also ==
 
== See also ==
Line 27: Line 99:
 
[[Category:Intermediate Combinatorics Problems]]
 
[[Category:Intermediate Combinatorics Problems]]
 
[[Category:Intermediate Number Theory Problems]]
 
[[Category:Intermediate Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 00:23, 26 December 2022

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.

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, our bad strings can take the forms: \begin{align*} &\underbrace{BA^{[10]}}\square \square \square \square \square \square \square\\ &\square \underbrace{BA^{[10]}}\square \square \square \square \square \square \\ &\qquad \quad \cdots \quad \cdots \\ &\square \square \square \square \square \square \underbrace{BA^{[10]}} \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^9(2^9-1)-8\cdot 2^7 = 2^{18} - 2^9 - 8 \cdot 2^7 = 2^9 \times 509$, and the answer is $\boxed{511}$.

Note: This solution is quick and most similar to the official solution; however, neither this nor the official solution prove that the final results of these inverted operations are all distinct. A more sophisticated argument, such as the one below, is needed to do so.

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{A}_{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 (valid if $n\ne 11$), 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}.\] The first relation will only be valid if $n\ne 12$. Therefore, $S_n=2S_{n-1}-S_{n-11}$ for $n\ge 13$. For smaller values, it is easy to use the relations to compute that the terms are powers of $2$, although we note that $A_{11,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}$.

See also

2004 AIME I (ProblemsAnswer KeyResources)
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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png