Difference between revisions of "2004 AIME I Problems/Problem 15"
Mathgeek2006 (talk | contribs) |
Mathgeek2006 (talk | contribs) m (→Solution 2) |
||
Line 34: | Line 34: | ||
Next, we claim that if <math>n\ge 3</math>, then | 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> | <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{n,0}</math>. | + | 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 | Based on these bijections, if we let <math>A_{n,k}=|\mathcal{A}_{n,k}|</math>, then | ||
Line 46: | Line 46: | ||
A_{n,9}&=A_{n-1,0}. | A_{n,9}&=A_{n-1,0}. | ||
\end{align*}</cmath> | \end{align*}</cmath> | ||
− | Let <math>S_n=\sum_{k=0}^9 A_{n,k}</math>. Then by adding the above equations, we find that | + | 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> | <cmath>S_n=2S_{n-1}-A_{n-1,1}.</cmath> | ||
Now by using the above relations repeatedly, we find | 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> | <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> | ||
− | Therefore, <math>S_n=2S_{n-1}-S_{n-11}</math> for <math>n\ge | + | 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_{10,1}=0</math> because of the failure of the above argument. |
<cmath>\begin{array}{c|cccccccccc|c} | <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 | 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 |
Revision as of 23:38, 24 February 2016
Problem
For all positive integers , let and define a sequence as follows: and for all positive integers . Let be the smallest such that . (For example, and .) Let be the number of positive integers such that . Find the sum of the distinct prime factors of .
Solution
Solution 1
We backcount the number of ways. Namely, we start at , which can only be reached if , and then we perform operations that either consist of or . We represent these operations in a string format, starting with the operation that sends and so forth downwards. There are ways to pick the first operations; however, not all of them may be otherwise we return back to , contradicting our assumption that was the smallest value of . Using complementary counting, we see that there are only ways.
Since we performed the operation at least once in the first operations, it follows that , so that we no longer have to worry about reaching again. Thus the remaining operations can be picked in ways, with a total of strings.
However, we must also account for a sequence of or more s in a row, because that implies that at least one of those numbers was divisible by , yet the was never used, contradiction. We must use complementary counting again by determining the number of strings of s of length such that there are s in a row. The first ten are not included since we already accounted for that scenario above, so our string of s must be preceded by a . There are no other restrictions on the remaining seven characters. Letting to denote either of the functions, and to indicate that the character appears times in a row, then our bad strings can take the forms:
There are ways to select the operations for the s, and places to place our block. Thus, our answer is , and the answer is .
Solution 2
We approach the problem by recursion. We partition the positive integers into the sets First, we note that , so by the disjointness of the 's, we know that is not in any of the other sets. Also, we note that for .
We claim that if and , then . To prove this, we show that (the given function) maps bijectively onto . If , then , and , so . Also, , where is the smallest positive integer for which this is true. Therefore, , where is the smallest integer for which this is true. Thus . Also, since on this set, we see that implies that . Hence is an injection. If , then , where , so we know that , and . Therefore, is a surjection, so it must be a bijection. Therefore, if and , then .
We also claim that if , and , then . The proof is the same as in the previous paragraph, though some additional clarification is needed to prove that is a surjection. If , or rather , then if , we see that , and then , not as in the prior argument. However, this does not happen if . It is easy to check that . Therefore, the only time that the above argument could fail is if and . But in every other case, .
Next, we claim that if , then If , then , which is clearly an injective map. Also, , where is the smallest positive integer for which this is true. Therefore, , where is the smallest integer for which this is true. Thus for some . Conversely, if , then , so , so .
Based on these bijections, if we let , then Let . Then by adding the above equations (valid if ), we find that Now by using the above relations repeatedly, we find The first relation will only be valid if . Therefore, for . For smaller values, it is easy to use the relations to compute that the terms are powers of , although we note that because of the failure of the above argument. After this, we can simply use the recurrence relation for , finding Therefore, there are positive integers with . This factors as , where is prime. Thus the answer is .
See also
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.