Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2007 AMC 12A Problems/Problem 22"
(→‎Solution 4)
Line 63: Line 63:
  
 
===Solution 4===
 
===Solution 4===
−
*This solution is not a good solution, but is viable for in contest situations
+
Claim. The only positive integers <math>n</math> that satisfy the condition are perfect multiples of <math>3</math>.
−
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.
+
Proof of claim:
 +
We examine the positive integers mod <math>9</math>. Here are the cases.
 +
 
 +
Case 1. <math>n \equiv 1 \pmod 9</math>. Now, we examine <math>S(n)</math> modulo <math>9</math>.
 +
Case 1.1. The tens digit of <math>n</math> is different from the tens digit of the largest multiple of <math>9</math> under <math>n</math>. (In other words, this means we will carry when adding from the perfect multiple of <math>9</math> under <math>n</math>.)
 +
Observe that when we carry, i.e. Add <math>1</math> onto <math>1989</math> to obtain <math>1990</math>, the units digit decreases by <math>9</math> while the tens digit increases by <math>1</math>. This means that the sum of the digits decreases by <math>8</math> in total, and we have <math>-8 \equiv 1 \pmod 9</math>, so the "mod 9" of the sum increases by <math>1</math>. This means that, regardless of whether the sum carries or not, the modulo 9 of the sum of the digits always increases by <math>1</math>.
 +
 
 +
Case 1.2. The tens digits are the same, which is trivial since the units digit just increases by <math>1</math> which means that the sum is also equivalent to <math>1 \pmod 9</math>.
 +
 
 +
This means that <math>S(n) \equiv 1 \pmod 9</math> and similarly letting the next <math>n=S(n)</math>, <math>S(S(n)) \equiv 1 \pmod 9</math>. Summing these, we have <math>n+S(n)+S(S(n)) \equiv 3 \pmod 9</math>. Clearly, no integers of this form will satisfy the condition because <math>2007</math> is a perfect multiple of <math>9</math>.
 +
 
 +
Case 2. <math>n \equiv 2 \pmod 9</math>.
 +
 
 +
In this case, we apply exactly the same argument. There is at most one carry, which means that the sum of the digits will always be congruent to <math>2</math> mod <math>9</math>. Then we can apply similar arguments to get <math>S(n) \equiv 2 \pmod 9</math> and <math>S(S(n)) \equiv 2 \pmod 9</math>, so adding gives <math>n+S(n)+S(S(n)) \equiv 6 \pmod 9</math>.
 +
 
 +
It is trivial to see that for <math>n \equiv k \pmod 9</math>, for <math>0 \leq k \leq 8</math>, we must have <math>n+S(n)+S(S(n)) \equiv 3k \pmod 9</math>. Only when <math>k=0, 3, 6</math> is <math>3k</math> a multiple of <math>9</math>, which means that <math>n</math> must be a multiple of <math>3</math>.
 +
 
 +
Now, we find the integers. Again, consider two cases: Integers that are direct multiples of <math>9</math> and integers that are multiples of <math>3</math> but not <math>9</math>.
 +
 
 +
Case 1. <math>n</math> is a multiple of <math>9</math>. An integer of the form <math>\overline{20ab}</math> will not work since the least such integer is <math>2007</math> which already exceeds our bounds. Thus, we need only consider the integers of the form <math>\overline{19ab}</math>. The valid sums of the digits of <math>n</math> are <math>18</math> and <math>27</math> in this case.
 +
 
 +
Case 1.1. The sum of the digits is <math>18</math>. This means that <math>S(n)=18, S(S(n))=9</math>, so <math>n=2007-18-9=1980</math>. Clearly this number satisfies our constraints.
 +
 
 +
Case 1.2. The sum of the digits is <math>27</math>. This means that <math>S(n)=27, S(S(n))=9</math>, ,so <math>n=2007-27-9=1971</math>. Since the sum of the digits of <math>1971</math> is not <math>27</math>, this does not work.
 +
 
 +
This means that there is <math>1</math> integer in this case.
 +
 
 +
Case 2. <math>n</math> is a multiple of <math>3</math>, not <math>9</math>.
 +
.
 +
Case 2.1. Integers of the form <math>\overline{20ab}</math>. Then <math>S(n)=3</math> or <math>S(n)=6</math>; it is trivial to see that <math>S(n)=6</math> exceeds our bounds, so <math>S(n)=3</math> and <math>n=2007-6=2001</math>.
 +
 
 +
Case 2.2. Integers of the form <math>\overline{19ab}</math>. Then <math>S(n)=12, 15, 21, 24</math> and we consider each case separately.
 +
 
 +
Case 2.2.1. Integers with <math>S(n)=12</math>. That means <math>n=2007-12-3=1992</math> which clearly does not work.
 +
 
 +
Case 2.2.2. Integers with <math>S(n)=15</math>. That means <math>n=2007-15-6=1986</math> which also does not work
 +
 
 +
Case 2.2.3. Integers with <math>S(n)=21</math>. That means <math>n=2007-21-3=1983</math> which is valid.
 +
 
 +
Case 2.2.4. Integers with <math>S(n)=24</math>. That means <math>n=2007-24-6=1977</math> which is also valid.
 +
 
 +
We have considered every case, so there are <math>\boxed{4}</math> integers that satisfy the given condition.
 +
 
 +
~Refined by HamstPan38825
  
 
==Solution 5 (Rigorous)==
 
==Solution 5 (Rigorous)==

Revision as of 13:16, 16 December 2020

The following problem is from both the 2007 AMC 12A #22 and 2007 AMC 10A #25, so both problems redirect to this page.

Problem

For each positive integer $n$, let $S(n)$ denote the sum of the digits of $n.$ For how many values of $n$ is $n + S(n) + S(S(n)) = 2007?$

$\mathrm{(A)}\ 1 \qquad \mathrm{(B)}\ 2 \qquad \mathrm{(C)}\ 3 \qquad \mathrm{(D)}\ 4 \qquad \mathrm{(E)}\ 5$

Solution

Solution 1

For the sake of notation let $T(n) = n + S(n) + S(S(n))$. Obviously $n<2007$. Then the maximum value of $S(n) + S(S(n))$ is when $n = 1999$, and the sum becomes $28 + 10 = 38$. So the minimum bound is $1969$. We do casework upon the tens digit:

Case 1: $196u \Longrightarrow u = 9$. Easy to directly disprove.

Case 2: $197u$. $S(n) = 1 + 9 + 7 + u = 17 + u$, and $S(S(n)) = 8+u$ if $u \le 2$ and $S(S(n)) = 2 + (u-3) = u-1$ otherwise.

Subcase a: $T(n) = 1970 + u + 17 + u + 8 + u = 1995 + 3u = 2007 \Longrightarrow u = 4$. This exceeds our bounds, so no solution here.
Subcase b: $T(n) = 1970 + u + 17 + u + u - 1 = 1986 + 3u = 2007 \Longrightarrow u = 7$. First solution.

Case 3: $198u$. $S(n) = 18 + u$, and $S(S(n)) = 9 + u$ if $u \le 1$ and $2 + (u-2) = u$ otherwise.

Subcase a: $T(n) = 1980 + u + 18 + u + 9 + u = 2007 + 3u = 2007 \Longrightarrow u = 0$. Second solution.
Subcase b: $T(n) = 1980 + u + 18 + u + u = 1998 + 3u = 2007 \Longrightarrow u = 3$. Third solution.

Case 4: $199u$. But $S(n) > 19$, and $n + S(n)$ clearly sum to $> 2007$.

Case 5: $200u$. So $S(n) = 2 + u$ and $S(S(n)) = 2 + u$ (recall that $n < 2007$), and $2000 + u + 2 + u + 2 + u = 2004 + 3u = 2007 \Longrightarrow u = 1$. Fourth solution.

In total we have $4 \mathrm{(D)}$ solutions, which are $1977, 1980, 1983,$ and $2001$.

Solution 2

Clearly, $n > 1950$. We can break this into three cases:

Case 1: $n \geq 2000$

Inspection gives $n = 2001$.

Case 2: $n < 2000$, $n = 19xy$ (not to be confused with $19*x*y$), $x + y < 10$

If you set up an equation, it reduces to

$4x + y = 32$

which has as its only solution satisfying the constraints $x = 8$, $y = 0$.

Case 3: $n < 2000$, $n = 19xy$, $x + y \geq 10$

This reduces to
$4x + y = 35$. The only two solutions satisfying the constraints for this equation are $x = 7$, $y = 7$ and $x = 8$, $y = 3$.

The solutions are thus $1977, 1980, 1983, 2001$ and the answer is $\mathrm{(D)}\ 4$.

Solution 3

As in Solution 1, we note that $S(n)\leq 28$ and $S(S(n))\leq 10$.
Obviously, $n\equiv S(n)\equiv S(S(n)) \pmod 9$.
As $2007\equiv 0 \pmod 9$, this means that $n\bmod 9 \in\{0,3,6\}$, or equivalently that $n\equiv S(n)\equiv S(S(n))\equiv 0 \pmod 3$.

Thus $S(S(n))\in\{3,6,9\}$. For each possible $S(S(n))$ we get three possible $S(n)$.
(E. g., if $S(S(n))=6$, then $S(n)=x$ is a number such that $x\leq 28$ and $S(x)=6$, therefore $S(n)\in\{6,15,24\}$.)

For each of these nine possibilities we compute $n_{?}$ as $2007-S(n)-S(S(n))$ and check whether $S(n_{?})=S(n)$.
We'll find out that out of the 9 cases, in 4 the value $n_{?}$ has the correct sum of digits.
This happens for $n_{?}\in \{ 1977, 1980, 1983, 2001 \}$.

Solution 4

Claim. The only positive integers $n$ that satisfy the condition are perfect multiples of $3$.

Proof of claim: We examine the positive integers mod $9$. Here are the cases.

Case 1. $n \equiv 1 \pmod 9$. Now, we examine $S(n)$ modulo $9$. Case 1.1. The tens digit of $n$ is different from the tens digit of the largest multiple of $9$ under $n$. (In other words, this means we will carry when adding from the perfect multiple of $9$ under $n$.) Observe that when we carry, i.e. Add $1$ onto $1989$ to obtain $1990$, the units digit decreases by $9$ while the tens digit increases by $1$. This means that the sum of the digits decreases by $8$ in total, and we have $-8 \equiv 1 \pmod 9$, so the "mod 9" of the sum increases by $1$. This means that, regardless of whether the sum carries or not, the modulo 9 of the sum of the digits always increases by $1$.

Case 1.2. The tens digits are the same, which is trivial since the units digit just increases by $1$ which means that the sum is also equivalent to $1 \pmod 9$.

This means that $S(n) \equiv 1 \pmod 9$ and similarly letting the next $n=S(n)$, $S(S(n)) \equiv 1 \pmod 9$. Summing these, we have $n+S(n)+S(S(n)) \equiv 3 \pmod 9$. Clearly, no integers of this form will satisfy the condition because $2007$ is a perfect multiple of $9$.

Case 2. $n \equiv 2 \pmod 9$.

In this case, we apply exactly the same argument. There is at most one carry, which means that the sum of the digits will always be congruent to $2$ mod $9$. Then we can apply similar arguments to get $S(n) \equiv 2 \pmod 9$ and $S(S(n)) \equiv 2 \pmod 9$, so adding gives $n+S(n)+S(S(n)) \equiv 6 \pmod 9$.

It is trivial to see that for $n \equiv k \pmod 9$, for $0 \leq k \leq 8$, we must have $n+S(n)+S(S(n)) \equiv 3k \pmod 9$. Only when $k=0, 3, 6$ is $3k$ a multiple of $9$, which means that $n$ must be a multiple of $3$.

Now, we find the integers. Again, consider two cases: Integers that are direct multiples of $9$ and integers that are multiples of $3$ but not $9$.

Case 1. $n$ is a multiple of $9$. An integer of the form $\overline{20ab}$ will not work since the least such integer is $2007$ which already exceeds our bounds. Thus, we need only consider the integers of the form $\overline{19ab}$. The valid sums of the digits of $n$ are $18$ and $27$ in this case.

Case 1.1. The sum of the digits is $18$. This means that $S(n)=18, S(S(n))=9$, so $n=2007-18-9=1980$. Clearly this number satisfies our constraints.

Case 1.2. The sum of the digits is $27$. This means that $S(n)=27, S(S(n))=9$, ,so $n=2007-27-9=1971$. Since the sum of the digits of $1971$ is not $27$, this does not work.

This means that there is $1$ integer in this case.

Case 2. $n$ is a multiple of $3$, not $9$. . Case 2.1. Integers of the form $\overline{20ab}$. Then $S(n)=3$ or $S(n)=6$; it is trivial to see that $S(n)=6$ exceeds our bounds, so $S(n)=3$ and $n=2007-6=2001$.

Case 2.2. Integers of the form $\overline{19ab}$. Then $S(n)=12, 15, 21, 24$ and we consider each case separately.

Case 2.2.1. Integers with $S(n)=12$. That means $n=2007-12-3=1992$ which clearly does not work.

Case 2.2.2. Integers with $S(n)=15$. That means $n=2007-15-6=1986$ which also does not work

Case 2.2.3. Integers with $S(n)=21$. That means $n=2007-21-3=1983$ which is valid.

Case 2.2.4. Integers with $S(n)=24$. That means $n=2007-24-6=1977$ which is also valid.

We have considered every case, so there are $\boxed{4}$ integers that satisfy the given condition.

~Refined by HamstPan38825

Solution 5 (Rigorous)

Let the number of digits of $n$ be $m$. If $m = 5$, $n$ will already be greater than $2007$. Notice that $S(n)$ is always at most $9m$. Then if $m = 3$, $n$ will be at most $999$, $S(n)$ will be at most $27$, and $S(S(n))$ will be even smaller than $27$. Clearly we cannot reach a sum of $2007$, unless $m = 4$ (i.e. $n$ has $4$ digits).

Then, let $n$ be a four digit number in the form $1000a + 100b + 10c + d$. Then $S(n) = a + b + c + d$.

$S(S(n))$ is the sum of the digits of $a + b + c + d$. We can represent $S(S(n))$ as the sum of the tens digit and the ones digit of $S(n)$. The tens digit in the form of a decimal is


$\frac{a + b + c + d}{10}$.


To remove the decimal portion, we can simply take the floor of the expression,


$\lfloor\frac{a + b + c + d}{10}\rfloor$.


Now that we have expressed the tens digit, we can express the ones digit as $S(S(n)) -10$ times the above expression, or


$a + b + c + d - 10\lfloor\frac{a + b + c + d}{10}\rfloor$.


Adding the two expressions yields the value of $S(S(n))$


$= a + b + c + d - 9\lfloor\frac{a + b + c + d}{10}\rfloor$.


Combining this expression to the ones for $n$ and $S(n)$ yields


$1002a + 102b + 12c + 3d - 9\lfloor\frac{a + b + c + d}{10}\rfloor$.


Setting this equal to $2007$ and rearranging a bit yields


$12c + 3d = 2007 - 1002a - 102b + 9\lfloor\frac{a + b + c + d}{10}\rfloor$

$\Rightarrow$ $4c + d = 669 - 334a - 34b + 3\lfloor\frac{a + b + c + d}{10}\rfloor$.


(The reason for this slightly weird arrangement will soon become evident)


Now we examine the possible values of $a$. If $a \ge 3$, $n$ is already too large. $a$ must also be greater than $0$, or $n$ would be a $3$-digit number. Therefore, $a = 1 \, \text{or} \, 2$. Now we examine by case.

If $a = 2$, then $b$ and $c$ must both be $0$ (otherwise $n$ would already be greater than $2007$). Substituting these values into the equation yields


$d = 1 + 3\lfloor\frac{2 + d}{10}\rfloor$

$\Rightarrow$ $d=1$.


Sure enough, $2001 + (2+1) + 3=2007$.

Now we move onto the case where $a = 1$. Then our initial equation simplifies to


$4c + d = 335 - 34b + 3\lfloor\frac{1 + b + c + d}{10}\rfloor$


Since $c$ and $d$ can each be at most $9$, we substitute that value to find the lower bound of $b$. Doing so yields


$34b \ge 290 + 3\lfloor\frac{19 + b}{10}\rfloor$.


The floor expression is at least $3\lfloor\frac{19}{10}\rfloor=3$ , so the right-hand side is at least $293$. Solving for $b$, we see that $b \ge 9$ $\Rightarrow$ $b=9$. Again, we substitute for $b$ and the equation becomes


$4c + d = 29 + 3\lfloor\frac{10 + c + d}{10}\rfloor$

$\Rightarrow$ $4c + d = 32 + 3\lfloor\frac{c + d}{10}\rfloor$.


Just like we did for $b$, we can find the lower bound of $c$ by assuming $d = 9$ and solving:


$4c + 9 \ge 29 + 3\lfloor\frac{c + 9}{10}\rfloor$

$\Rightarrow$ $4c \ge 20 + 3\lfloor\frac{c + 9}{10}\rfloor$


The right hand side is $20$ for $c=0$ and $23$ for $c \ge 1$. Solving for c yields $c \ge 6$. Looking back at the previous equation, the floor expression is $0$ for $c+d \le 9$ and $3$ for $c+d \ge 10$. Thus, the right-hand side is $32$ for $c+d \le 9$ and $35$ for $c+d \ge 10$. We can solve these two scenarios as systems of equations/inequalities:

$4c+d = 32$

$c+d \le 9$

and

$4c+d=35$

$c+d \ge 10$

Solving yields three pairs $(c, d):$ $(8, 0)$; $(8, 3)$; and $(7, 7)$. Checking the numbers $1980$, $1983$, and $1977$; we find that all three work. Therefore there are a total of $4$ possibilities for $n$ $\Rightarrow$ $\boxed{\text{D}}$.

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 $\boxed{\text{D}}$

-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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2007_AMC_12A_Problems/Problem_22&oldid=139793"