2007 AMC 12A Problems/Problem 22

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

This solution is not a good solution, but is viable for in contest situations

Clearly $n\equiv S(n) \pmod 9$ . Thus, $n+S(n)+S(S(n))\equiv 0 \pmod 9 \implies n\equiv 0\pmod 3.$ Now we need a bound for $n$ . It is clear that the maximum for $S(n)=36$ (from $n=9999$ ) which means the maximum for $S(n)+S(S(n))$ is $45$ . This means that $n\geq 1962$ .

Warning: This is where you will cringe badly

Now check all multiples of $3$ from $1962$ to $2007$ and we find that only $n=1977, 1980, 1983, 2001$ work, so our answer is $\mathrm{(D)}\ 4$ .

Remark: this may seem time consuming, but in reality, calculating $n+S(n)+S(S(n))$ for $16$ 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 $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.

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

Page

Toolbox

Search