Difference between revisions of "2015 AIME I Problems/Problem 8"
(→Solution) |
(→Solution) |
||
Line 44: | Line 44: | ||
So the answer is <math>\boxed{695}</math> which after a quick test, does indeed work. | So the answer is <math>\boxed{695}</math> which after a quick test, does indeed work. | ||
+ | |||
+ | ==Solution 2== | ||
+ | First, it is easy to verify that <math>695</math> works and that no other numbers beginning with the digit 6 work (i.e. <math>686, 677, 668, 659</math> do not work). | ||
+ | |||
+ | Suppose by contradiction that there is a smaller valid <math>n</math>, where the leading digit of the three-digit number <math>n</math> is 5 or less. (Two-digit <math>n</math> obviously do not work because 9 + 9 < 20.) Clearly <math>n > 200</math> because the smallest three-digit number whose digits sum to 20 is <math>299</math>. Also, because the second digit is at most 9, the units digit is at least 6, which means that the addition <math>N = n + 864</math> regroups in the ones place. Then the units digit of <math>N</math> is clearly less than 4. But as <math>1000 < 200 + 864 < N < 600 + 864 = 1464</math>, the sum of the thousands digit and the hundredth digit is at most 5. Because the second digit is at most 9, the sum of the digits of <math>N</math> is at most <math>5 + 9 + 4 < 20</math>, contradiction. Hence <math>\boxed{695}</math> is the answer. | ||
+ | |||
+ | ==Motivation for Solution 2== | ||
+ | During the real test, I immediately noticed that <math>n</math> must be less than 1000 (AIME problem) and that <math>n</math> must be a three-digit number. Therefore, I began casework on the leading digit of <math>n</math>. The casework was not intensive (how many ways are there to have digits sum to 20?) and I eventually got 695 as my answer. The rigorous proof that 695 was the smallest came afterwards. | ||
== See also == | == See also == |
Revision as of 17:32, 20 March 2015
Problem
For positive integer , let denote the sum of the digits of . Find the smallest positive integer satisfying .
Solution
You know whatever is, it has to have 3 digits, because if it had only two, the maximum of is 18.
Now let
So first we know, . Okay now we have to split into cases based on which digit gets carried. This meaning, when you add a 3 digit number to 864, we have to know when to carry the digits. Note that if you don't understand any of the steps I take, just try adding any 3-digit number to 864 regularly (using the old-fashioned "put one number over the other" method, not mental calculation), and observe what you do at each step.
(1) None of the digit gets carried over to the next space: So this means and . So
So it doesn't work. Now:
(2) is the only one that carries over So this means and . So
(3) is the only one that carries over. So
(4)The first and second digit carry over (but not the third)
Aha! This case works but we still have to make sure it's possible for (We assumed this is true, so we have to find a number that works.) Since only the second and first digit carry over, and . The smallest value we can get with this is 695. Let's see if we can find a smaller one:
(5)The first and third digit carry over (but not the second)
The largest value for the middle digit is 2, so the other digits have to be both 9's. So the smallest possible value is 929
(6) All the digits carry over
So the answer is which after a quick test, does indeed work.
Solution 2
First, it is easy to verify that works and that no other numbers beginning with the digit 6 work (i.e. do not work).
Suppose by contradiction that there is a smaller valid , where the leading digit of the three-digit number is 5 or less. (Two-digit obviously do not work because 9 + 9 < 20.) Clearly because the smallest three-digit number whose digits sum to 20 is . Also, because the second digit is at most 9, the units digit is at least 6, which means that the addition regroups in the ones place. Then the units digit of is clearly less than 4. But as , the sum of the thousands digit and the hundredth digit is at most 5. Because the second digit is at most 9, the sum of the digits of is at most , contradiction. Hence is the answer.
Motivation for Solution 2
During the real test, I immediately noticed that must be less than 1000 (AIME problem) and that must be a three-digit number. Therefore, I began casework on the leading digit of . The casework was not intensive (how many ways are there to have digits sum to 20?) and I eventually got 695 as my answer. The rigorous proof that 695 was the smallest came afterwards.
See also
2015 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 7 |
Followed by Problem 9 | |
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.