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 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: ,
- 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 (Fastest casework)
It is well-known that Substituting, we have that Since we must have that Now, we list out the possible vales for in a table, noting that it is a multiple of because is a multiple of
Then, we compute the corresponding values of
Finally, we may compute the corresponding values of using the fact that
Notice how all conditions are designed to be satisfied except whether is accurate with respect to So, the only thing that remains is to check this. We may eliminate, for example, when we have while the table states that it is Proceeding similarly, we obtain the following table.
It follows that there are possible values for ~samrocksnature
Solution 4
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 5
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 6 (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.
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.