Difference between revisions of "2015 AIME II Problems/Problem 3"
(One intermediate revision by one other user not shown) | |||
Line 85: | Line 85: | ||
<cmath>17|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>. | 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 14: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.