2015 AIME II Problems/Problem 3
Let be the least positive integer divisible by whose digits sum to . Find .
The three-digit integers divisible by , and their digit sum:
Thus the answer is .
Solution 2 (Shortcut)
We can do the same thing as solution 1, except note the following fact: is a multiple of and its digits sum to .
Therefore, we can add it onto an existing multiple of that we know of to have , shown in the right-hand column, provided that its units digit is less than and its hundreds digit is less than . Unfortunately, does not fit the criteria, but does, meaning that, instead of continually adding multiples of , we can stop here and simply add to reach our final answer of .
(Comment from another person: Actually, this doesn't work because you can't be sure there are no numbers between 374 and 476 that work. This solution just lucks out.)
The digit sum of a base integer is just . In this problem, we know , or for a positive integer .
Also, we know that , or .
Obviously is a solution. This means in general, is a solution for non-negative integer .
Checking the first few possible solutions, we find that is the first solution that has , and we're done.
Since the sum of the digits in the base-10 representation of is , we must have or . We also know that since is divisible by 17, .
To solve this system of linear congruences, we can use the Chinese Remainder Theorem. If we set , we find that and , because . The trick to getting here was to find the number such that , so that when we take things , the goes away. We can do this using the Extended Euclidean Algorithm or by guess and check to find that .
Finally, since , we repeatedly add multiples of until we get a number in which its digits sum to 17, which first happens when .
We proceed by casework on the number of digits. Clearly the answer must have at least two digits, seeing as the maximum digit sum for a one-digit number is 9. The answer must also have less than 4 digits, because this is the AIME.
Case 1: The answer is a 2-digit number. Represent the number as , where and . The conditions of the problem translated into algebra are: By the Euclidean Algorithm, this is equivalent to: 9 is not a factor of 17, so . So must be a multiple of 17, but this is impossible because of the conditions we placed on and . (Alternatively, note that the only possible options are 89 and 98, and neither works.)
Case 2: The answer is a 3-digit number. Represent the number as , where and . Translating the conditions again: Testing multiples of 17 yields as the minimal solution for and thus the answer is .
|2015 AIME II (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|