Difference between revisions of "2017 AMC 10A Problems/Problem 25"
m (→Solution 2) |
(→Solution 1) |
||
(18 intermediate revisions by 5 users not shown) | |||
Line 5: | Line 5: | ||
==Solution 1== | ==Solution 1== | ||
− | There are 81 multiples of 11. Some have digits repeated twice, making 3 permutations. | + | There are 81 multiples of 11 between <math>100</math> and <math>999</math> inclusive. Some have digits repeated twice, making 3 permutations. |
− | Others that have no repeated digits have 6 permutations, but switching the hundreds and units digits also yield a multiple of 11. | + | Others that have no repeated digits have 6 permutations, but switching the hundreds and units digits also yield a multiple of 11. Switching shows we have overcounted by a factor of 2, so assign <math>6 \div 2 = 3</math> permutations to each multiple. |
− | There are now 81*3 = 243 permutations, but we have overcounted*. Some multiples of 11 have a | + | There are now 81*3 = 243 permutations, but we have overcounted*. Some multiples of 11 have <math>0</math> as a digit. Since <math>0</math> cannot be the digit of the hundreds place, we must subtract a permutation for each. |
There are 110, 220, 330 ... 990, yielding 9 extra permutations | There are 110, 220, 330 ... 990, yielding 9 extra permutations | ||
Line 15: | Line 15: | ||
Also, there are 209, 308, 407...902, yielding 8 more permutations. | Also, there are 209, 308, 407...902, yielding 8 more permutations. | ||
− | Now, just subtract these 17 from the total (243) | + | Now, just subtract these 17 from the total (243) to get 226. <math>\boxed{\textbf{(A) } 226}</math> |
− | *Note: If short on time, | + | *Note: If short on time, observe that 226 is the only answer choice less than 243, and therefore is the only feasible answer. |
− | + | ==Solution 2== | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
We note that we only have to consider multiples of <math>11</math> and see how many valid permutations each has. We can do casework on the number of repeating digits that the multiple of <math>11</math> has: | We note that we only have to consider multiples of <math>11</math> and see how many valid permutations each has. We can do casework on the number of repeating digits that the multiple of <math>11</math> has: | ||
Line 89: | Line 43: | ||
Adding up all the permutations from all the cases, we have <math>24+18+16+168 = \boxed{\textbf{(A) } 226}</math>. | Adding up all the permutations from all the cases, we have <math>24+18+16+168 = \boxed{\textbf{(A) } 226}</math>. | ||
− | ==Solution | + | ==Solution 3 == |
We can first overcount and then subtract. | We can first overcount and then subtract. | ||
Line 118: | Line 72: | ||
Now, we may ask if there is further overlap (i.e if two of <math>abc</math> and <math>bac</math> and <math>acb</math> were multiples of <math>11</math>). Thankfully, using divisibility rules, this can never happen, as taking the divisibility rule mod <math>11</math> and adding, we get that <math>2a</math>, <math>2b</math>, or <math>2c</math> is congruent to <math>0\ (mod\ 11)</math>. Since <math>a, b, c</math> are digits, this can never happen as none of them can equal <math>11</math> and they can't equal <math>0</math> as they are the leading digit of a three-digit number in each of the cases. | Now, we may ask if there is further overlap (i.e if two of <math>abc</math> and <math>bac</math> and <math>acb</math> were multiples of <math>11</math>). Thankfully, using divisibility rules, this can never happen, as taking the divisibility rule mod <math>11</math> and adding, we get that <math>2a</math>, <math>2b</math>, or <math>2c</math> is congruent to <math>0\ (mod\ 11)</math>. Since <math>a, b, c</math> are digits, this can never happen as none of them can equal <math>11</math> and they can't equal <math>0</math> as they are the leading digit of a three-digit number in each of the cases. | ||
− | == Solution | + | == Solution 4 (1 but quicker) == |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | The smallest multiple of <math>11</math> above <math>100</math> is <math>110 = 11 \cdot 10</math>, while the largest multiple of <math>11</math> less than <math>999</math> is <math>990 = 11 \cdot 90</math>. This means there are <math>90 - 10 + 1 = 81</math> multiples of <math>11</math> between <math>100</math> and <math>999</math>. | |
− | < | ||
− | |||
− | + | As there are <math>3</math> permutations for each multiple, we have <math>81 * 3 = 243</math>. However, we have overcounted, as numbers like <math>099</math> shouldn't be counted. Looking at the answer choices, we notice there is only one that is less than <math>243</math>, and so we have our answer as <math>\boxed{\textbf{(A) } 226}</math>. | |
− | + | -¢ | |
==Video Solution== | ==Video Solution== |
Latest revision as of 17:16, 24 July 2021
Contents
Problem
How many integers between and , inclusive, have the property that some permutation of its digits is a multiple of between and For example, both and have this property.
Solution 1
There are 81 multiples of 11 between and inclusive. Some have digits repeated twice, making 3 permutations.
Others that have no repeated digits have 6 permutations, but switching the hundreds and units digits also yield a multiple of 11. Switching shows we have overcounted by a factor of 2, so assign permutations to each multiple.
There are now 81*3 = 243 permutations, but we have overcounted*. Some multiples of 11 have as a digit. Since cannot be the digit of the hundreds place, we must subtract a permutation for each.
There are 110, 220, 330 ... 990, yielding 9 extra permutations
Also, there are 209, 308, 407...902, yielding 8 more permutations.
Now, just subtract these 17 from the total (243) to get 226.
- Note: If short on time, observe that 226 is the only answer choice less than 243, and therefore is the only feasible answer.
Solution 2
We note that we only have to consider multiples of and see how many valid permutations each has. We can do casework on the number of repeating digits that the multiple of has:
All three digits are the same. By inspection, we find that there are no multiples of here.
Two of the digits are the same, and the third is different.
There are multiples of without a zero that have this property: , , , , , , , . Each contributes valid permutations, so there are permutations in this subcase.
There are multiples of with a zero that have this property: , , , , , , , , . Each one contributes valid permutations (the first digit can't be zero), so there are permutations in this subcase.
All the digits are different. Since there are multiples of between and , there are multiples of remaining in this case. However, of them contain a zero, namely , , , , , , , and . Each of those multiples of contributes valid permutations, but we overcounted by a factor of ; every permutation of , for example, is also a permutation of . Therefore, there are . Therefore, there are remaining multiples of without a in this case. Each one contributes valid permutations, but once again, we overcounted by a factor of (note that if a number ABC is a multiple of , then so is CBA). Therefore, there are valid permutations in this subcase.
Adding up all the permutations from all the cases, we have .
Solution 3
We can first overcount and then subtract. We know that there are multiples of .
We can then multiply by for each permutation of these multiples. (Yet some multiples do not have six distinct permutations.)
Now divide by , because if a number with digits , , and is a multiple of , then is also a multiple of so we have counted the same permutations twice.
Basically, each multiple of has its own permutations (say has and whereas has and ). We know that each multiple of has at least permutations because it cannot have repeating digits.
Hence we have permutations without subtracting for overcounting. Now note that we overcounted cases in which we have 's at the start of each number. So, in theory, we could just answer and then move on.
If we want to solve it, then we continue.
We overcounted cases where the middle digit of the number is and the last digit is .
Note that we assigned each multiple of three permutations.
The last digit is gives possibilities where we overcounted by permutation for each of .
The middle digit is gives possibilities where we overcount by . and
Subtracting gives .
Now, we may ask if there is further overlap (i.e if two of and and were multiples of ). Thankfully, using divisibility rules, this can never happen, as taking the divisibility rule mod and adding, we get that , , or is congruent to . Since are digits, this can never happen as none of them can equal and they can't equal as they are the leading digit of a three-digit number in each of the cases.
Solution 4 (1 but quicker)
The smallest multiple of above is , while the largest multiple of less than is . This means there are multiples of between and .
As there are permutations for each multiple, we have . However, we have overcounted, as numbers like shouldn't be counted. Looking at the answer choices, we notice there is only one that is less than , and so we have our answer as .
-¢
Video Solution
Two different variations on solving it. https://youtu.be/z5KNZEwmrWM
https://youtu.be/MBcHwu30MX4 -Video Solution by Richard Rusczyk
~savannahsolver
See Also
2017 AMC 10A (Problems • Answer Key • Resources) | ||
Preceded by Problem 24 |
Followed by Last Problem | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | ||
All AMC 10 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.