2015 AIME II Problems/Problem 3

Revision as of 17:56, 5 June 2020 by Frestho (talk | contribs) (Solution 2 (Shortcut))
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

See also

2015 AIME II (ProblemsAnswer KeyResources)
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

Invalid username
Login to AoPS