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.
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
Claim. The only positive integers that satisfy the condition are perfect multiples of .
Proof of claim: We examine the positive integers mod . Here are the cases.
Case 1. . Now, we examine modulo . Case 1.1. The tens digit of is different from the tens digit of the largest multiple of under . (In other words, this means we will carry when adding from the perfect multiple of under .) Observe that when we carry, i.e. Add onto to obtain , the units digit decreases by while the tens digit increases by . This means that the sum of the digits decreases by in total, and we have , so the "mod 9" of the sum increases by . This means that, regardless of whether the sum carries or not, the modulo 9 of the sum of the digits always increases by .
Case 1.2. The tens digits are the same, which is trivial since the units digit just increases by which means that the sum is also equivalent to .
This means that and similarly letting the next , . Summing these, we have . Clearly, no integers of this form will satisfy the condition because is a perfect multiple of .
Case 2. .
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 mod . Then we can apply similar arguments to get and , so adding gives .
It is trivial to see that for , for , we must have . Only when is a multiple of , which means that must be a multiple of .
Now, we find the integers. Again, consider two cases: Integers that are direct multiples of and integers that are multiples of but not .
Case 1. is a multiple of . An integer of the form will not work since the least such integer is which already exceeds our bounds. Thus, we need only consider the integers of the form . The valid sums of the digits of are and in this case.
Case 1.1. The sum of the digits is . This means that , so . Clearly this number satisfies our constraints.
Case 1.2. The sum of the digits is . This means that , ,so . Since the sum of the digits of is not , this does not work.
This means that there is integer in this case.
Case 2. is a multiple of , not . . Case 2.1. Integers of the form . Then or ; it is trivial to see that exceeds our bounds, so and .
Case 2.2. Integers of the form . Then and we consider each case separately.
Case 2.2.1. Integers with . That means which clearly does not work.
Case 2.2.2. Integers with . That means which also does not work
Case 2.2.3. Integers with . That means which is valid.
Case 2.2.4. Integers with . That means which is also valid.
We have considered every case, so there are integers that satisfy the given condition.
~Refined by HamstPan38825
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.