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

Revision as of 17:33, 18 January 2018

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

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 3

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}$ .

@@ Line 44: / Line 44: @@
 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 3==
+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>.
 == See also ==
 {{AIME box|year=2015|n=II|num-b=2|num-a=4}} {{MAA Notice}}

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

Page

Toolbox

Search