Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2017 AMC 10A Problems/Problem 25"
(→‎=Solution 3 (Shorter and Not Casework))
Line 75: Line 75:
 
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 3 (Shorter and Not Casework)=
+
==Solution 3 (Shorter and Not Casework)==
  
 
We can overcount and then subtract.
 
We can overcount and then subtract.
Line 82: Line 82:
 
We can multiply be 6 for each permutation of these multiples.
 
We can multiply be 6 for each permutation of these multiples.
  
−
Now divide by 2, as if a number abc with digits a, b and c is a multiple of 11, then cab is also a multiple of 11 so we have counted the same permutations twice. So basically we say that each multiple of 11 has 3 permutations (say abc has abc acb and bac where's cab has cab cba and bca).
+
Now divide by 2, as if a number abc with digits a, b and c is a multiple of 11, then cab is also a multiple of 11 so we have counted the same permutations twice.  
  
−
Hence we have 243. Now note that we overcounted cases is which we have 0's at the start of each number. So in theory we could just answer A and move on.
+
So basically we say that each multiple of 11 has it own 3 permutations (say abc has abc acb and bac where's cab has cab cba and bca).
  
 +
Hence we have 243 permutations.
 +
Now note that we overcounted cases is which we have 0's at the start of each number. So in theory we could just answer A and move on.
 +
 +
We can also solve it :/
 
We overcount cases where the Middle digit of the number is 0 and the last digit is 0.
 
We overcount cases where the Middle digit of the number is 0 and the last digit is 0.
  
Line 97: Line 101:
 
Subtracting 17 gives 226 or A.
 
Subtracting 17 gives 226 or A.
  
−
Now, we may ask if there is further overlap (I.e if two of abc and bac and acb were  multiples of 11) Thankfully, using divisibility rules, this can never happen as taking the divisibility rule mod 11 and adding we get that 2a,2b or 2c is congruent to 0 mod 11. Since abc are digits, this can never happen.
+
Now, we may ask if there is further overlap (I.e if two of abc and bac and acb were  multiples of 11) Thankfully, using divisibility rules, this can never happen as taking the divisibility rule mod 11 and adding we get that 2a,2b or 2c is congruent to 0 mod 11. Since a,b,c are digits, this can never happen as none of them can equal 11 and they can't equal 0 as they are the leading digit of a 3 digit number in each of the cases
  
 
==See Also==
 
==See Also==
 
{{AMC10 box|year=2017|ab=A|num-b=24|after=Last Problem}}
 
{{AMC10 box|year=2017|ab=A|num-b=24|after=Last Problem}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 21:49, 8 February 2017

Problem

How many integers between $100$ and $999$, inclusive, have the property that some permutation of its digits is a multiple of $11$ between $100$ and $999?$ For example, both $121$ and $211$ have this property.

$\mathrm{(A) \ }226\qquad \mathrm{(B) \ } 243 \qquad \mathrm{(C) \ } 270 \qquad \mathrm{(D) \ }469\qquad \mathrm{(E) \ } 486$

Solution 1

Let the three-digit number be $ACB$:

If a number is divisible by $11$, then the difference between the sums of alternating digits is a multiple of $11$.

There are two cases: $A+B=C$ and $A+B=C+11$

We now proceed to break down the cases.


$\textbf{Case 1}$: $A+B=C$. This has $18+45+33+21+9=126$ cases.


$\textbf{Part 1}$: $B=0$ $A=C$, this case results in 110, 220, 330...990. There are two ways to arrange the digits in each of those numbers. $2 \cdot 9 = 18$

$\textbf{Part 2}$: $B>0$ $B=1, A+1=C$, this case results in 121, 231,... 891. There are $6$ ways to arrange the digits in all of those number except the first, and 3 ways ways for the first. This leads to $45$ cases.

$\textbf{Part 3}$: $B=2, A+2=C$, this case results in 242, 352,... 792. There are $6$ ways to arrange the digits in all of those number except the first, and 3 ways ways for the first. This leads to $33$ cases.

$\textbf{Part 4}$: $B=3, A+3=C$, this case results in 363, 473,...693. There are $6$ ways to arrange the digits in all of those number except the first, and 3 ways ways for the first. This leads to $21$ cases.

$\textbf{Part 5}$: $B=4, A+4=C$, this case results in 484 and 594. There are $6$ ways to arrange the digits in all of those number except the first, and 3 ways ways for the first. This leads to $9$ cases.


$\textbf{Case 2}$: $A+B=C+11$.


$\textbf{Part 1}$: $C=0, A+B=11$, this cases results in 209, 308, ...506. There are $4$ ways to arrange each of those cases. This leads to $16$ cases.

$\textbf{Part 2}$: $C=1, A+B=12$, this cases results in 319, 418, ...616. There are $6$ ways to arrange each of those cases, except the last. This leads to $21$ cases.

$\textbf{Part 3}$: $C=2, A+B=13$, this cases results in 429, 528, ...617. There are $6$ ways to arrange each of those cases. This leads to $18$ cases.

... If you continue this counting, you receive $16+21+18+15+12+9+6+3=100$ cases.

$100+126=\boxed{\textbf{(A) } 226}$

-Solution by Mathguy1492

Solution 2

We note that we only have to consider multiples of 11 and see how many valid permutations each has. We can do casework on the number of repeating digits that the multiple of 11 has:

$\textbf{Case 1:}$ All three digits are the same. By inspection, we find that there are no multiples of 11 here.

$\textbf{Case 2:}$ Two of the digits are the same, and the third is different.

$\textbf{Case 2a:}$ There are 8 multiples of 11 without a zero that have this property: 121, 242, 363, 484, 616, 737, 858, 979. Each contributes 3 valid permutations, so there are $8 \cdot 3 = 24$ permutations in this subcase.

$\textbf{Case 2b:}$ There are 9 multiples of 11 with a zero that have this property: 110, 220, 330, 440, 550, 660, 770, 880, 990. Each one contributes 2 valid permutations (the first digit can't be zero), so there are $9 \cdot 2 = 18$ permutations in this subcase.

$\textbf{Case 3:}$ All the digits are different. Since there are $\frac{990-110}{11}+1 = 81$ multiples of 11 between 100 and 999, there are $81-8-9 = 64$ multiples of 11 remaining in this case. However, 8 of them contain a zero, namely 209, 308, 407, 506, 605, 704, 803, and 902. Each of those multiples of 11 contributes $2 \cdot 2=4$ valid permutations, but we overcounted by a factor of 2; every permutation of 209, for example, is also a permutation of 902. Therefore, there are $8 \cdot 4 / 2 = 16$. Therefore, there are $64-8=56$ remaining multiples of 11 without a 0 in this case. Each one contributes $3! = 6$ valid permutations, but once again, we overcounted by a factor of 2 (note that if a number ABC is a multiple of 11, then so is CBA). Therefore, there are $56 \cdot 6 / 2 = 168$ valid permutations in this subcase.

Adding up all the permutations from all the cases, we have $24+18+16+168 = \boxed{\textbf{(A) } 226}$.

Solution 3 (Shorter and Not Casework)

We can overcount and then subtract. We know there are 81 multiples of 11.

We can multiply be 6 for each permutation of these multiples.

Now divide by 2, as if a number abc with digits a, b and c is a multiple of 11, then cab is also a multiple of 11 so we have counted the same permutations twice.

So basically we say that each multiple of 11 has it own 3 permutations (say abc has abc acb and bac where's cab has cab cba and bca).

Hence we have 243 permutations. 

Now note that we overcounted cases is which we have 0's at the start of each number. So in theory we could just answer A and move on.

We can also solve it :/ We overcount cases where the Middle digit of the number is 0 and the last digit is 0.

Note that we assigned each multiple of 11 3 permutations.

The last digit is 0 gives 9 possibilities where we overcount by 1 permutation for each of 110,220, ... , 990.

The middle digit is 0 gives 8 possibilities where we overcount by 1. 605, 704, 803, 902 and 506, 407, 308, 209

Subtracting 17 gives 226 or A.

Now, we may ask if there is further overlap (I.e if two of abc and bac and acb were multiples of 11) Thankfully, using divisibility rules, this can never happen as taking the divisibility rule mod 11 and adding we get that 2a,2b or 2c is congruent to 0 mod 11. Since a,b,c are digits, this can never happen as none of them can equal 11 and they can't equal 0 as they are the leading digit of a 3 digit number in each of the cases

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2017_AMC_10A_Problems/Problem_25&oldid=83211"