Difference between revisions of "2007 AMC 12A Problems/Problem 22"
m (→Solution 2: (blank edit) 2nd solution by Jacob Steinhardt) |
Alexlikemath (talk | contribs) |
||
(26 intermediate revisions by 15 users not shown) | |||
Line 1: | Line 1: | ||
+ | {{duplicate|[[2007 AMC 12A Problems|2007 AMC 12A #22]] and [[2007 AMC 10A Problems/Problem 25|2007 AMC 10A #25]]}} | ||
== Problem == | == Problem == | ||
− | For each positive integer <math>n</math>, let <math>S(n)</math> denote the sum of the digits of <math>n.</math> For how many values of <math>n</math> is <math> | + | For each positive integer <math>n</math>, let <math>S(n)</math> denote the sum of the digits of <math>n.</math> For how many values of <math>n</math> is <math>n + S(n) + S(S(n)) = 2007?</math> |
<math>\mathrm{(A)}\ 1 \qquad \mathrm{(B)}\ 2 \qquad \mathrm{(C)}\ 3 \qquad \mathrm{(D)}\ 4 \qquad \mathrm{(E)}\ 5</math> | <math>\mathrm{(A)}\ 1 \qquad \mathrm{(B)}\ 2 \qquad \mathrm{(C)}\ 3 \qquad \mathrm{(D)}\ 4 \qquad \mathrm{(E)}\ 5</math> | ||
− | |||
== Solution == | == Solution == | ||
=== Solution 1 === | === Solution 1 === | ||
− | For the sake of notation let <math>T(n) = n + S(n) + S(S(n))</math>. Obviously <math>n<2007</math>. Then the maximum value of <math> | + | For the sake of notation let <math>T(n) = n + S(n) + S(S(n))</math>. Obviously <math>n<2007</math>. Then the maximum value of <math>S(n) + S(S(n))</math> is when <math>n = 1999</math>, and the sum becomes <math>28 + 10 = 38</math>. So the minimum bound is <math>1969</math>. We do [[casework]] upon the tens digit: |
Case 1: <math>196u \Longrightarrow u = 9</math>. Easy to directly disprove. | Case 1: <math>196u \Longrightarrow u = 9</math>. Easy to directly disprove. | ||
− | Case 2: <math>197u</math>. <math>S(n) = 1 + 9 + 7 + u = 17 + u</math>, and <math>S(S(n)) = 8+u</math> if <math>u \le 2</math> and <math> | + | Case 2: <math>197u</math>. <math>S(n) = 1 + 9 + 7 + u = 17 + u</math>, and <math>S(S(n)) = 8+u</math> if <math>u \le 2</math> and <math>S(S(n)) = 2 + (u-3) = u-1</math> otherwise. |
:Subcase a: <math>T(n) = 1970 + u + 17 + u + 8 + u = 1995 + 3u = 2007 \Longrightarrow u = 4</math>. This exceeds our bounds, so no solution here. | :Subcase a: <math>T(n) = 1970 + u + 17 + u + 8 + u = 1995 + 3u = 2007 \Longrightarrow u = 4</math>. This exceeds our bounds, so no solution here. | ||
− | :Subcase b: <math> | + | :Subcase b: <math>T(n) = 1970 + u + 17 + u + u - 1 = 1986 + 3u = 2007 \Longrightarrow u = 7</math>. First solution. |
− | Case 3: <math>198u</math>. <math>S(n) = 18 + u</math>, and <math>S(S(n)) = 9 + u</math> if <math>u \le 1</math> and <math> | + | Case 3: <math>198u</math>. <math>S(n) = 18 + u</math>, and <math>S(S(n)) = 9 + u</math> if <math>u \le 1</math> and <math>2 + (u-2) = u</math> otherwise. |
− | :Subcase a: <math> | + | :Subcase a: <math>T(n) = 1980 + u + 18 + u + 9 + u = 2007 + 3u = 2007 \Longrightarrow u = 0</math>. Second solution. |
:Subcase b: <math>T(n) = 1980 + u + 18 + u + u = 1998 + 3u = 2007 \Longrightarrow u = 3</math>. Third solution. | :Subcase b: <math>T(n) = 1980 + u + 18 + u + u = 1998 + 3u = 2007 \Longrightarrow u = 3</math>. Third solution. | ||
− | Case 4: <math>199u</math>. But <math>S(n) > 19</math>, and | + | Case 4: <math>199u</math>. But <math>S(n) > 19</math>, and <math>n + S(n)</math> clearly sum to <math>> 2007</math>. |
− | Case 5: <math>200u</math>. So <math>S(n) = 2 + u</math> and <math>S(S(n)) = 2 + u</math>, and <math> | + | Case 5: <math>200u</math>. So <math>S(n) = 2 + u</math> and <math>S(S(n)) = 2 + u</math> (recall that <math>n < 2007 </math>), and <math>2000 + u + 2 + u + 2 + u = 2004 + 3u = 2007 \Longrightarrow u = 1</math>. Fourth solution. |
In total we have <math>4 \mathrm{(D)}</math> solutions, which are <math>1977, 1980, 1983, </math> and <math>2001</math>. | In total we have <math>4 \mathrm{(D)}</math> solutions, which are <math>1977, 1980, 1983, </math> and <math>2001</math>. | ||
=== Solution 2 === | === Solution 2 === | ||
− | Clearly, <math>n > | + | Clearly, <math>n > 1950</math>. We can break this into three cases: |
Case 1: <math>n \geq 2000</math> | Case 1: <math>n \geq 2000</math> | ||
− | :Inspection gives <math> | + | :Inspection gives <math>n = 2001</math>. |
− | Case 2: <math> | + | Case 2: <math>n < 2000</math>, <math>n = 19xy</math> (not to be confused with <math>19*x*y</math>), <math>x + y < 10 </math> |
:If you set up an equation, it reduces to | :If you set up an equation, it reduces to | ||
Line 42: | Line 42: | ||
:which has as its only solution satisfying the constraints <math>x = 8</math>, <math>y = 0</math>. | :which has as its only solution satisfying the constraints <math>x = 8</math>, <math>y = 0</math>. | ||
− | Case 3: <math> | + | Case 3: <math>n < 2000</math>, <math>n = 19xy</math>, <math>x + y \geq 10</math> |
:This reduces to | :This reduces to | ||
− | :<math> | + | :<math>4x + y = 35</math>. The only two solutions satisfying the constraints for this equation are <math>x = 7</math>, <math>y = 7</math> and <math>x = 8</math>, <math>y = 3</math>. |
The solutions are thus <math>1977, 1980, 1983, 2001</math> and the answer is <math>\mathrm{(D)}\ 4</math>. | The solutions are thus <math>1977, 1980, 1983, 2001</math> and the answer is <math>\mathrm{(D)}\ 4</math>. | ||
+ | |||
+ | === Solution 3 === | ||
+ | As in Solution 1, we note that <math>S(n)\leq 28</math> and <math>S(S(n))\leq 10</math>. <br/> | ||
+ | Obviously, <math>n\equiv S(n)\equiv S(S(n)) \pmod 9</math>. <br/> | ||
+ | As <math>2007\equiv 0 \pmod 9</math>, this means that <math>n\bmod 9 \in\{0,3,6\}</math>, or equivalently that <math>n\equiv S(n)\equiv S(S(n))\equiv 0 \pmod 3</math>. | ||
+ | |||
+ | Thus <math>S(S(n))\in\{3,6,9\}</math>. For each possible <math>S(S(n))</math> we get three possible <math>S(n)</math>. <br/> | ||
+ | (E. g., if <math>S(S(n))=6</math>, then <math>S(n)=x</math> is a number such that <math>x\leq 28</math> and <math>S(x)=6</math>, therefore <math>S(n)\in\{6,15,24\}</math>.) | ||
+ | |||
+ | For each of these nine possibilities we compute <math>n_{?}</math> as <math>2007-S(n)-S(S(n))</math> and check whether <math>S(n_{?})=S(n)</math>. <br/> | ||
+ | We'll find out that out of the 9 cases, in 4 the value <math>n_{?}</math> has the correct sum of digits. <br/> | ||
+ | This happens for <math>n_{?}\in \{ 1977, 1980, 1983, 2001 \}</math>. | ||
+ | |||
+ | ===Solution 4=== | ||
+ | *This solution is not a good solution, but is viable for in contest situations | ||
+ | Clearly <math>n\equiv S(n) \pmod 9</math>. Thus, <cmath>n+S(n)+S(S(n))\equiv 0 \pmod 9 \implies n\equiv 0\pmod 3.</cmath> | ||
+ | Now we need a bound for <math>n</math>. It is clear that the maximum for <math>S(n)=36</math> (from <math>n=9999</math>) which means the maximum for <math>S(n)+S(S(n))</math> is <math>45</math>. This means that <math>n\geq 1962</math>. | ||
+ | *Warning: This is where you will cringe badly | ||
+ | Now check all multiples of <math>3</math> from <math>1962</math> to <math>2007</math> and we find that only <math>n=1977, 1980, 1983, 2001</math> work, so our answer is <math>\mathrm{(D)}\ 4</math>. | ||
+ | |||
+ | Remark: this may seem time consuming, but in reality, calculating <math>n+S(n)+S(S(n))</math> for <math>16</math> values is actually very quick, so this solution would only take approximately 3-5 minutes, helpful in a contest. | ||
+ | |||
+ | ==Solution 5 (Rigorous)== | ||
+ | Let the number of digits of <math>n</math> be <math>m</math>. If <math>m = 5</math>, <math>n</math> will already be greater than <math>2007</math>. Notice that <math>S(n)</math> is always at most <math>9m</math>. Then if <math>m = 3</math>, <math>n</math> will be at most <math>999</math>, <math>S(n)</math> will be at most <math>27</math>, and <math>S(S(n))</math> will be even smaller than <math>27</math>. Clearly we cannot reach a sum of <math>2007</math>, unless <math>m = 4</math> (i.e. <math>n</math> has <math>4</math> digits). | ||
+ | |||
+ | Then, let <math>n</math> be a four digit number in the form <math>1000a + 100b + 10c + d</math>. Then <math>S(n) = a + b + c + d</math>. | ||
+ | |||
+ | <math>S(S(n))</math> is the sum of the digits of <math>a + b + c + d</math>. We can represent <math>S(S(n))</math> as the sum of the tens digit and the ones digit of <math>S(n)</math>. The tens digit in the form of a decimal is | ||
+ | |||
+ | |||
+ | <math>\frac{a + b + c + d}{10}</math>. | ||
+ | |||
+ | |||
+ | To remove the decimal portion, we can simply take the floor of the expression, | ||
+ | |||
+ | |||
+ | <math>\lfloor\frac{a + b + c + d}{10}\rfloor</math>. | ||
+ | |||
+ | |||
+ | Now that we have expressed the tens digit, we can express the ones digit as <math>S(S(n)) -10</math> times the above expression, or | ||
+ | |||
+ | |||
+ | <math>a + b + c + d - 10\lfloor\frac{a + b + c + d}{10}\rfloor</math>. | ||
+ | |||
+ | |||
+ | Adding the two expressions yields the value of <math>S(S(n))</math> | ||
+ | |||
+ | |||
+ | <math> = a + b + c + d - 9\lfloor\frac{a + b + c + d}{10}\rfloor</math>. | ||
+ | |||
+ | |||
+ | Combining this expression to the ones for <math>n</math> and <math>S(n)</math> yields | ||
+ | |||
+ | |||
+ | <math>1002a + 102b + 12c + 3d - 9\lfloor\frac{a + b + c + d}{10}\rfloor</math>. | ||
+ | |||
+ | |||
+ | Setting this equal to <math>2007</math> and rearranging a bit yields | ||
+ | |||
+ | |||
+ | <math>12c + 3d = 2007 - 1002a - 102b + 9\lfloor\frac{a + b + c + d}{10}\rfloor</math> | ||
+ | |||
+ | <math>\Rightarrow</math> <math>4c + d = 669 - 334a - 34b + 3\lfloor\frac{a + b + c + d}{10}\rfloor</math>. | ||
+ | |||
+ | |||
+ | (The reason for this slightly weird arrangement will soon become evident) | ||
+ | |||
+ | |||
+ | Now we examine the possible values of <math>a</math>. If <math>a \ge 3</math>, <math>n</math> is already too large. <math>a</math> must also be greater than <math>0</math>, or <math>n</math> would be a <math>3</math>-digit number. Therefore, <math>a = 1 \, \text{or} \, 2</math>. Now we examine by case. | ||
+ | |||
+ | If <math>a = 2</math>, then <math>b</math> and <math>c</math> must both be <math>0</math> (otherwise <math>n</math> would already be greater than <math>2007</math>). Substituting these values into the equation yields | ||
+ | |||
+ | |||
+ | <math>d = 1 + 3\lfloor\frac{2 + d}{10}\rfloor</math> | ||
+ | |||
+ | <math>\Rightarrow</math> <math>d=1</math>. | ||
+ | |||
+ | |||
+ | Sure enough, <math>2001 + (2+1) + 3=2007</math>. | ||
+ | |||
+ | Now we move onto the case where <math>a = 1</math>. Then our initial equation simplifies to | ||
+ | |||
+ | |||
+ | <math>4c + d = 335 - 34b + 3\lfloor\frac{1 + b + c + d}{10}\rfloor</math> | ||
+ | |||
+ | |||
+ | Since <math>c</math> and <math>d</math> can each be at most <math>9</math>, we substitute that value to find the lower bound of <math>b</math>. Doing so yields | ||
+ | |||
+ | |||
+ | <math>34b \ge 290 + 3\lfloor\frac{19 + b}{10}\rfloor</math>. | ||
+ | |||
+ | |||
+ | The floor expression is at least <math>3\lfloor\frac{19}{10}\rfloor=3</math> , so the right-hand side is at least <math>293</math>. Solving for <math>b</math>, we see that <math>b \ge 9 </math> <math>\Rightarrow</math> <math>b=9</math>. Again, we substitute for <math>b</math> and the equation becomes | ||
+ | |||
+ | |||
+ | <math>4c + d = 29 + 3\lfloor\frac{10 + c + d}{10}\rfloor</math> | ||
+ | |||
+ | <math>\Rightarrow</math> <math>4c + d = 32 + 3\lfloor\frac{c + d}{10}\rfloor</math>. | ||
+ | |||
+ | |||
+ | Just like we did for <math>b</math>, we can find the lower bound of <math>c</math> by assuming <math>d = 9</math> and solving: | ||
+ | |||
+ | |||
+ | <math>4c + 9 \ge 29 + 3\lfloor\frac{c + 9}{10}\rfloor</math> | ||
+ | |||
+ | <math>\Rightarrow</math> <math>4c \ge 20 + 3\lfloor\frac{c + 9}{10}\rfloor</math> | ||
+ | |||
+ | |||
+ | The right hand side is <math>20</math> for <math>c=0</math> and <math>23</math> for <math>c \ge 1</math>. Solving for c yields <math>c \ge 6</math>. Looking back at the previous equation, the floor expression is <math>0</math> for <math>c+d \le 9</math> and <math>3</math> for <math>c+d \ge 10</math>. Thus, the right-hand side is <math>32</math> for <math>c+d \le 9</math> and <math>35</math> for <math>c+d \ge 10</math>. We can solve these two scenarios as systems of equations/inequalities: | ||
+ | |||
+ | <math>4c+d = 32</math> | ||
+ | |||
+ | <math>c+d \le 9</math> | ||
+ | |||
+ | and | ||
+ | |||
+ | <math>4c+d=35</math> | ||
+ | |||
+ | <math>c+d \ge 10</math> | ||
+ | |||
+ | Solving yields three pairs <math>(c, d):</math> <math>(8, 0)</math>; <math>(8, 3)</math>; and <math>(7, 7)</math>. Checking the numbers <math>1980</math>, <math>1983</math>, and <math>1977</math>; we find that all three work. Therefore there are a total of <math>4</math> possibilities for <math>n</math> <math>\Rightarrow</math> <math>\boxed{\text{D}}</math>. | ||
+ | |||
+ | Note: Although this solution takes a while to read (as well as to write) the actual time it takes to think through the process above is very short in comparison to the solution length. | ||
+ | |||
+ | ==Solution 6== | ||
+ | |||
+ | |||
+ | Rearranging, we get | ||
+ | 2007 - S(n) - S(S(n)) = n. | ||
+ | |||
+ | We can now try S(n) = 1-28, to find values of n. Then, you need to check whether S(n) = sum digits of n. If so, you found a solution! | ||
+ | |||
+ | The bash involves making a table with 3 columns: S(n), n, S(n). We write the numbers 1-28 in the S(n) column, we can find n using the above equation, and the third column we can just find the sum of the digits of n, and if the first column/3rd column match, we have a solution. | ||
+ | |||
+ | You will in the end find S(n) = 3, 18, 21, 24 yield solutions, which corrispond to n = 2001, 1980, 1983, 1977. There are 4 solutions, so the answer is <math>\boxed{\text{D}}</math> | ||
+ | |||
+ | -Alexlikemath | ||
== See also == | == See also == | ||
{{AMC12 box|year=2007|ab=A|num-b=21|num-a=23}} | {{AMC12 box|year=2007|ab=A|num-b=21|num-a=23}} | ||
+ | {{AMC10 box|year=2007|ab=A|num-b=24|after=Last question}} | ||
[[Category:Introductory Number Theory Problems]] | [[Category:Introductory Number Theory Problems]] | ||
+ | {{MAA Notice}} |
Revision as of 00:42, 31 August 2020
- The following problem is from both the 2007 AMC 12A #22 and 2007 AMC 10A #25, so both problems redirect to this page.
Contents
Problem
For each positive integer , let denote the sum of the digits of For how many values of is
Solution
Solution 1
For the sake of notation let . Obviously . Then the maximum value of is when , and the sum becomes . So the minimum bound is . We do casework upon the tens digit:
Case 1: . Easy to directly disprove.
Case 2: . , and if and otherwise.
- Subcase a: . This exceeds our bounds, so no solution here.
- Subcase b: . First solution.
Case 3: . , and if and otherwise.
- Subcase a: . Second solution.
- Subcase b: . Third solution.
Case 4: . But , and clearly sum to .
Case 5: . So and (recall that ), and . Fourth solution.
In total we have solutions, which are and .
Solution 2
Clearly, . We can break this into three cases:
Case 1:
- Inspection gives .
Case 2: , (not to be confused with ),
- If you set up an equation, it reduces to
- which has as its only solution satisfying the constraints , .
Case 3: , ,
- This reduces to
- . The only two solutions satisfying the constraints for this equation are , and , .
The solutions are thus and the answer is .
Solution 3
As in Solution 1, we note that and .
Obviously, .
As , this means that , or equivalently that .
Thus . For each possible we get three possible .
(E. g., if , then is a number such that and , therefore .)
For each of these nine possibilities we compute as and check whether .
We'll find out that out of the 9 cases, in 4 the value has the correct sum of digits.
This happens for .
Solution 4
- This solution is not a good solution, but is viable for in contest situations
Clearly . Thus, Now we need a bound for . It is clear that the maximum for (from ) which means the maximum for is . This means that .
- Warning: This is where you will cringe badly
Now check all multiples of from to and we find that only work, so our answer is .
Remark: this may seem time consuming, but in reality, calculating for values is actually very quick, so this solution would only take approximately 3-5 minutes, helpful in a contest.
Solution 5 (Rigorous)
Let the number of digits of be . If , will already be greater than . Notice that is always at most . Then if , will be at most , will be at most , and will be even smaller than . Clearly we cannot reach a sum of , unless (i.e. has digits).
Then, let be a four digit number in the form . Then .
is the sum of the digits of . We can represent as the sum of the tens digit and the ones digit of . The tens digit in the form of a decimal is
.
To remove the decimal portion, we can simply take the floor of the expression,
.
Now that we have expressed the tens digit, we can express the ones digit as times the above expression, or
.
Adding the two expressions yields the value of
.
Combining this expression to the ones for and yields
.
Setting this equal to and rearranging a bit yields
.
(The reason for this slightly weird arrangement will soon become evident)
Now we examine the possible values of . If , is already too large. must also be greater than , or would be a -digit number. Therefore, . Now we examine by case.
If , then and must both be (otherwise would already be greater than ). Substituting these values into the equation yields
.
Sure enough, .
Now we move onto the case where . Then our initial equation simplifies to
Since and can each be at most , we substitute that value to find the lower bound of . Doing so yields
.
The floor expression is at least , so the right-hand side is at least . Solving for , we see that . Again, we substitute for and the equation becomes
.
Just like we did for , we can find the lower bound of by assuming and solving:
The right hand side is for and for . Solving for c yields . Looking back at the previous equation, the floor expression is for and for . Thus, the right-hand side is for and for . We can solve these two scenarios as systems of equations/inequalities:
and
Solving yields three pairs ; ; and . Checking the numbers , , and ; we find that all three work. Therefore there are a total of possibilities for .
Note: Although this solution takes a while to read (as well as to write) the actual time it takes to think through the process above is very short in comparison to the solution length.
Solution 6
Rearranging, we get 2007 - S(n) - S(S(n)) = n.
We can now try S(n) = 1-28, to find values of n. Then, you need to check whether S(n) = sum digits of n. If so, you found a solution!
The bash involves making a table with 3 columns: S(n), n, S(n). We write the numbers 1-28 in the S(n) column, we can find n using the above equation, and the third column we can just find the sum of the digits of n, and if the first column/3rd column match, we have a solution.
You will in the end find S(n) = 3, 18, 21, 24 yield solutions, which corrispond to n = 2001, 1980, 1983, 1977. There are 4 solutions, so the answer is
-Alexlikemath
See also
2007 AMC 12A (Problems • Answer Key • Resources) | |
Preceded by Problem 21 |
Followed by Problem 23 |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | |
All AMC 12 Problems and Solutions |
2007 AMC 10A (Problems • Answer Key • Resources) | ||
Preceded by Problem 24 |
Followed by Last question | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | ||
All AMC 10 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.