Difference between revisions of "2015 AIME II Problems/Problem 3"
(Created page with "==Problem== Let <math>m</math> be the least positive integer divisible by <math>17</math> whose digits sum to <math>17</math>. Find <math>m</math>. ==Solution== == See als...") |
|||
(12 intermediate revisions by 5 users not shown) | |||
Line 3: | Line 3: | ||
Let <math>m</math> be the least positive integer divisible by <math>17</math> whose digits sum to <math>17</math>. Find <math>m</math>. | Let <math>m</math> be the least positive integer divisible by <math>17</math> whose digits sum to <math>17</math>. Find <math>m</math>. | ||
− | ==Solution== | + | ==Solution 1== |
+ | The three-digit integers divisible by <math>17</math>, and their digit sum: <cmath> | ||
+ | \begin{array}{c|c} | ||
+ | m & s(m)\\ \hline | ||
+ | 102 & 3 \\ | ||
+ | 119 & 11\\ | ||
+ | 136 & 10\\ | ||
+ | 153 & 9\\ | ||
+ | 170 & 8\\ | ||
+ | 187 & 16\\ | ||
+ | 204 & 6\\ | ||
+ | 221 & 5\\ | ||
+ | 238 & 13\\ | ||
+ | 255 & 12\\ | ||
+ | 272 & 11\\ | ||
+ | 289 & 19\\ | ||
+ | 306 & 9\\ | ||
+ | 323 & 8\\ | ||
+ | 340 & 7\\ | ||
+ | 357 & 15\\ | ||
+ | 374 & 14\\ | ||
+ | 391 & 13\\ | ||
+ | 408 & 12\\ | ||
+ | 425 & 11\\ | ||
+ | 442 & 10\\ | ||
+ | 459 & 18\\ | ||
+ | 476 & 17 | ||
+ | \end{array} | ||
+ | </cmath> | ||
+ | |||
+ | Thus the answer is <math>\boxed{476}</math>. | ||
+ | |||
+ | ==Solution 2 (Shortcut)== | ||
+ | |||
+ | We can do the same thing as solution 1, except note the following fact: <math>102</math> is a multiple of <math>17</math> and its digits sum to <math>3</math>. | ||
+ | |||
+ | Therefore, we can add it onto an existing multiple of <math>17</math> that we know of to have <math>s(m) = 14</math>, shown in the right-hand column, provided that its units digit is less than <math>8</math> and its hundreds digit is less than <math>9</math>. Unfortunately, <math>68</math> does not fit the criteria, but <math>374</math> does, meaning that, instead of continually adding multiples of <math>17</math>, we can stop here and simply add <math>102</math> to reach our final answer of <math>\boxed{476}</math>. | ||
+ | |||
+ | ~Tiblis | ||
+ | |||
+ | (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.) | ||
+ | |||
+ | ==Solution 3== | ||
+ | |||
+ | The digit sum of a base <math>10</math> integer <math>m</math> is just <math>m\pmod{9}</math>. In this problem, we know <math>17\mid m</math>, or <math>m=17k</math> for a positive integer <math>k</math>. | ||
+ | |||
+ | Also, we know that <math>m\equiv 17\equiv -1\pmod{9}</math>, or <math>17k\equiv -k\equiv -1\pmod{9}</math>. | ||
+ | |||
+ | Obviously <math>k=1</math> is a solution. This means in general, <math>k=9x+1</math> is a solution for non-negative integer <math>x</math>. | ||
+ | |||
+ | Checking the first few possible solutions, we find that <math>m=\boxed{476}</math> is the first solution that has <math>s(m)=17</math>, and we're done. | ||
+ | |||
+ | ==Solution 4== | ||
+ | |||
+ | Since the sum of the digits in the base-10 representation of <math>m</math> is <math>17</math>, we must have <math>m\equiv 17 \pmod{9}</math> or <math>m\equiv -1\pmod{9}</math>. | ||
+ | We also know that since <math>m</math> is divisible by 17, <math>m\equiv 0 \pmod{17}</math>. | ||
+ | |||
+ | To solve this system of linear congruences, we can use the Chinese Remainder Theorem. If we set <math>m\equiv (-1)(17)(8)\pmod {153}</math>, we find that <math>m\equiv 0\pmod{17}</math> and <math>m\equiv -1\pmod{9}</math>, because <math>17\cdot 8\equiv 136 \equiv 1\pmod{9}</math>. The trick to getting here was to find the number <math>x</math> such that <math>17x\equiv 1\pmod{9}</math>, so that when we take things <math>\pmod{9}</math>, the <math>17</math> goes away. We can do this using the Extended Euclidean Algorithm or by guess and check to find that <math>x\equiv 8\pmod{9}</math>. | ||
+ | |||
+ | Finally, since <math>m\equiv 17\pmod{153}</math>, we repeatedly add multiples of <math>153</math> until we get a number in which its digits sum to 17, which first happens when <math>m=\boxed{476}</math>. | ||
+ | |||
+ | ==Solution 5== | ||
+ | |||
+ | 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 <math>10a + b</math>, where <math>0 < a \leq 9</math> and <math>0 \leq b \leq 9</math>. The conditions of the problem translated into algebra are: | ||
+ | <cmath>17|10a+b</cmath> | ||
+ | <cmath>a+b=17</cmath> | ||
+ | By the Euclidean Algorithm, this is equivalent to: | ||
+ | <cmath>17|9a</cmath> | ||
+ | 9 is not a factor of 17, so <math>17|a</math>. So <math>a</math> must be a multiple of 17, but this is impossible because of the conditions we placed on <math>a</math> and <math>b</math>. | ||
+ | (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 <math>100a+10b+c</math>, where <math>0 < a \leq 9</math> and <math>0 \leq b,c \leq 9</math>. Translating the conditions again: | ||
+ | <cmath>17|100a+10b+c</cmath> | ||
+ | <cmath>a+b+c=17</cmath> | ||
+ | <cmath>17|99a+9b</cmath> | ||
+ | <cmath>17|9(11a+b)</cmath> | ||
+ | <cmath>17|11a+b</cmath> | ||
+ | Testing multiples of 17 yields <math>(4, 7, 6)</math> as the minimal solution for <math>(a, b, c)</math> and thus the answer is <math>\boxed{476}</math>. | ||
+ | |||
+ | - gting | ||
+ | |||
+ | |||
+ | |||
+ | ==Video Solution== | ||
+ | https://www.youtube.com/watch?v=9re2qLzOKWk&t=133s | ||
+ | |||
+ | ~MathProblemSolvingSkills.com | ||
+ | |||
+ | |||
== See also == | == See also == | ||
{{AIME box|year=2015|n=II|num-b=2|num-a=4}} {{MAA Notice}} | {{AIME box|year=2015|n=II|num-b=2|num-a=4}} {{MAA Notice}} |
Latest revision as of 13:03, 14 February 2023
Contents
Problem
Let be the least positive integer divisible by whose digits sum to . Find .
Solution 1
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 .
~Tiblis
(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.)
Solution 3
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.
Solution 4
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 .
Solution 5
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 .
- gting
Video Solution
https://www.youtube.com/watch?v=9re2qLzOKWk&t=133s
~MathProblemSolvingSkills.com
See also
2015 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.