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 | + | 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, | + | 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: |
− | < | + | <cmath>\begin{align*} |
− | &\underbrace{BA^{[10]}} | + | &\underbrace{BA^{[10]}}\square \square \square \square \square \square \square\\ |
− | &\square \underbrace{BA^{[10]}} | + | &\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 \underbrace{BA^{[10]}} \square \\ |
− | & | + | &\square \square \square \square \square \square \square \underbrace{BA^{[10]}} \\ |
− | \end{align*}</ | + | \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 , 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.
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, 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 .
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 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.