Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2015 AIME II Problems/Problem 3"

(→‎Solution 1)
 
(10 intermediate revisions by 5 users not shown)
Line 6: Line 6:
 
The three-digit integers divisible by <math>17</math>, and their digit sum: <cmath>
 
The three-digit integers divisible by <math>17</math>, and their digit sum: <cmath>
 
\begin{array}{c|c}
 
\begin{array}{c|c}
−
m & s(m)\\
+
m & s(m)\\ \hline
 
102 & 3 \\
 
102 & 3 \\
 
119 & 11\\
 
119 & 11\\
Line 34: Line 34:
  
 
Thus the answer is <math>\boxed{476}</math>.
 
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

Problem

Let $m$ be the least positive integer divisible by $17$ whose digits sum to $17$. Find $m$.

Solution 1

The three-digit integers divisible by $17$, and their digit sum: \[\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}\]

Thus the answer is $\boxed{476}$.

Solution 2 (Shortcut)

We can do the same thing as solution 1, except note the following fact: $102$ is a multiple of $17$ and its digits sum to $3$.

Therefore, we can add it onto an existing multiple of $17$ that we know of to have $s(m) = 14$, shown in the right-hand column, provided that its units digit is less than $8$ and its hundreds digit is less than $9$. Unfortunately, $68$ does not fit the criteria, but $374$ does, meaning that, instead of continually adding multiples of $17$, we can stop here and simply add $102$ to reach our final answer of $\boxed{476}$.

~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 $10$ integer $m$ is just $m\pmod{9}$. In this problem, we know $17\mid m$, or $m=17k$ for a positive integer $k$.

Also, we know that $m\equiv 17\equiv -1\pmod{9}$, or $17k\equiv -k\equiv -1\pmod{9}$.

Obviously $k=1$ is a solution. This means in general, $k=9x+1$ is a solution for non-negative integer $x$.

Checking the first few possible solutions, we find that $m=\boxed{476}$ is the first solution that has $s(m)=17$, and we're done.

Solution 4

Since the sum of the digits in the base-10 representation of $m$ is $17$, we must have $m\equiv 17 \pmod{9}$ or $m\equiv -1\pmod{9}$. We also know that since $m$ is divisible by 17, $m\equiv 0 \pmod{17}$.

To solve this system of linear congruences, we can use the Chinese Remainder Theorem. If we set $m\equiv (-1)(17)(8)\pmod {153}$, we find that $m\equiv 0\pmod{17}$ and $m\equiv -1\pmod{9}$, because $17\cdot 8\equiv 136 \equiv 1\pmod{9}$. The trick to getting here was to find the number $x$ such that $17x\equiv 1\pmod{9}$, so that when we take things $\pmod{9}$, the $17$ goes away. We can do this using the Extended Euclidean Algorithm or by guess and check to find that $x\equiv 8\pmod{9}$.

Finally, since $m\equiv 17\pmod{153}$, we repeatedly add multiples of $153$ until we get a number in which its digits sum to 17, which first happens when $m=\boxed{476}$.

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 $10a + b$, where $0 < a \leq 9$ and $0 \leq b \leq 9$. The conditions of the problem translated into algebra are: \[17|10a+b\] \[a+b=17\] By the Euclidean Algorithm, this is equivalent to: \[17|9a\] 9 is not a factor of 17, so $17|a$. So $a$ must be a multiple of 17, but this is impossible because of the conditions we placed on $a$ and $b$. (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 $100a+10b+c$, where $0 < a \leq 9$ and $0 \leq b,c \leq 9$. Translating the conditions again: \[17|100a+10b+c\] \[a+b+c=17\] \[17|99a+9b\] \[17|9(11a+b)\] \[17|11a+b\] Testing multiples of 17 yields $(4, 7, 6)$ as the minimal solution for $(a, b, c)$ and thus the answer is $\boxed{476}$.

- 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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2015_AIME_II_Problems/Problem_3&oldid=189612"