2017 AMC 10A Problems/Problem 25
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. 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. Therefore, assign 3 permutations to each multiple.
There are now 81*3 = 243 permutations, but we have overcounted*. Some multiples of 11 have a zero, and 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), getting 226.
- Note: If short on time, note that 226 is the only answer choice less than 243, and therefore is the only feasible answer.
Solution 2
Let the three-digit number be :
If a number is divisible by , then the difference between the sums of alternating digits is a multiple of
.
There are two cases:
and
We now proceed to break down the cases. Note: let so that we avoid counting the same permutations and having to subtract them later.
:
.
:
, this case results in
. There are two ways to arrange the digits in each of those numbers.
:
, this case results in
. There are
ways to arrange the digits in all of those number except the first, and
ways for the first. This leads to
cases.
:
, this case results in
. There are
ways to arrange the digits in all of those number except the first, and 3 ways for the first. This leads to
cases.
:
, this case results in
. There are
ways to arrange the digits in all of those number except the first, and 3 ways for the first. This leads to
cases.
:
, this case results in
and
. There are
ways to arrange the digits in 594 and 3 ways for 484. This leads to
cases.
This case has subcases.
:
.
:
, this cases results in
. There are
ways to arrange each of those cases. This leads to
cases.
:
, this cases results in
. There are
ways to arrange each of those cases, except the last. This leads to
cases.
:
, this cases results in
. There are
ways to arrange each of those cases. This leads to
cases.
...
If we continue this counting, we receive subcases.
Solution 3
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 4
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 5: A Slightly Adjusted Version of Solution 2
If you do not feel comfortable looking at a massive amount of casework, please skip the solution.
Recalling the divisibility rule for , if we have a number
where
,
,
are digits, then
.
Notice that for any three-digit positive integer ,
, thus we have 2 possibilities:
and
.
Subcase :
We have these values for
From which we get
triples
. Counting every permutation, we have
possibilities.
Subcase :
,
We have
From which we get
possibilities.
Subcase :
We have
Since
can't be the hundreds digit, from here we get
possibilities. Summing up case
, we have
possibilities.
Subcase :
We have these values for
From which we get
possibilities.
Subcase :
,
We have
From which we get
possibilities.
Subcase :
We have
From which we get
possibilities. Summing up case
, we have
possibilities.
Adding the cases, we get a total of
possibilities.
~ Nafer
Video Solution
Two different variations on solving it. https://youtu.be/z5KNZEwmrWM
https://youtu.be/MBcHwu30MX4 -Video Solution by Richard Rusczyk
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.