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"

m (→‎Solution 3: Minor grammar fixes; LaTeX)
(→‎Solution 1)
Line 16: Line 16:
  
  
−
<math>\textbf{Case 1}</math>: <math>A+B=C</math>.  
+
<math>\textbf{Case </math>1<math>}</math>: <math>A+B=C</math>.  
  
  
  
−
<math>\textbf{Part 1}</math>: <math>B=0, A=C</math>, this case results in 110, 220, 330...990. There are two ways to arrange the digits in each of those numbers.
+
<math>\textbf{Part 1}</math>: <math>B=0, A=C</math>, this case results in <math>110, 220, 330...990</math>. There are two ways to arrange the digits in each of those numbers.
−
<math>2 \cdot 9 = 18</math>
+
<math>2 \cdot </math>9 = 18<math>
  
−
<math>\textbf{Part 2}</math>:
+
</math>\textbf{Part <math>2</math>}<math>:
−
<math>B=1, A+1=C</math>, this case results in 121, 231,... 891. There are <math>6</math> ways to arrange the digits in all of those number except the first, and 3 ways for the first. This leads to <math>45</math> cases.
+
</math>B=1, A+<math>1</math>=C<math>, this case results in </math>121, 231,... 891<math>. There are </math>6<math> ways to arrange the digits in all of those number except the first, and 3 ways for the first. This leads to </math>45<math> cases.
  
−
<math>\textbf{Part 3}</math>: <math>B=2, A+2=C</math>, this case results in 242, 352,... 792. There are <math>6</math> ways to arrange the digits in all of those number except the first, and 3 ways for the first. This leads to <math>33</math> cases.
+
</math>\textbf{Part <math>3</math>}<math>: </math>B=2, A+2=C<math>, this case results in </math>242, 352,... 792<math>. There are </math>6<math> ways to arrange the digits in all of those number except the first, and 3 ways for the first. This leads to </math>33<math> cases.
  
−
<math>\textbf{Part 4}</math>: <math>B=3, A+3=C</math>, this case results in 363, 473,...693. There are <math>6</math> ways to arrange the digits in all of those number except the first, and 3 ways for the first. This leads to <math>21</math> cases.
+
</math>\textbf{Part <math>4</math>}<math>: </math>B=3, A+3=C<math>, this case results in </math>363, 473,...693<math>. There are </math>6<math> ways to arrange the digits in all of those number except the first, and 3 ways for the first. This leads to </math>21<math> cases.
  
−
<math>\textbf{Part 5}</math>: <math>B=4, A+4=C</math>, this case results in 484 and 594. There are <math>6</math> ways to arrange the digits in 594 and 3 ways for 484. This leads to <math>9</math> cases.
+
</math>\textbf{Part <math>5</math>}<math>: </math>B=4, A+4=C<math>, this case results in </math>484<math> and </math>594<math>. There are </math>6<math> ways to arrange the digits in 594 and 3 ways for 484. This leads to </math>9<math> cases.
  
−
This case has <math>18+45+33+21+9=126</math> subcases.
+
This case has </math>18+45+33+21+9=126<math> subcases.
  
  
  
−
<math>\textbf{Case 2}</math>: <math>A+B=C+11</math>.  
+
</math>\textbf{Case <math>2</math>}<math>: </math>A+B=C+11<math>.  
  
  
−
<math>\textbf{Part 1}</math>: <math>C=0, A+B=11</math>, this cases results in 209, 308, 407, 506. There are <math>4</math> ways to arrange each of those cases. This leads to <math>16</math> cases.
+
</math>\textbf{Part <math>1</math>}<math>: </math>C=0, A+B=11<math>, this cases results in </math>209, 308, 407, 506<math>. There are </math>4<math> ways to arrange each of those cases. This leads to </math>16<math> cases.
  
−
<math>\textbf{Part 2}</math>: <math>C=1, A+B=12</math>, this cases results in 319, 418,517,616. There are <math>6</math> ways to arrange each of those cases, except the last. This leads to <math>21</math> cases.
+
</math>\textbf{Part <math>2</math>}<math>: </math>C=1, A+B=12<math>, this cases results in </math>319, 418,517,616<math>. There are </math>6<math> ways to arrange each of those cases, except the last. This leads to </math>21<math> cases.
  
−
<math>\textbf{Part 3}</math>: <math>C=2, A+B=13</math>, this cases results in 429, 528, 627. There are <math>6</math> ways to arrange each of those cases. This leads to <math>18</math> cases.
+
</math>\textbf{Part 3}<math>: </math>C=2, A+B=13<math>, this cases results in 429, 528, 627. There are </math>6<math> ways to arrange each of those cases. This leads to </math>18<math> cases.
  
 
...
 
...
−
If we continue this counting, we receive <math>16+21+18+15+12+9+6+3=100</math> subcases.
+
If we continue this counting, we receive </math>16+21+18+15+12+9+6+3=100<math> subcases.
  
−
<math>100+126=\boxed{\textbf{(A) } 226}</math>
+
</math>100+126=\boxed{\textbf{(A) } <math>226</math>}$
  
 
==Solution 2==
 
==Solution 2==

Revision as of 14:51, 2 January 2020

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{\textbf{(A)} \ }226\qquad \mathrm{\textbf{(B)} \ } 243 \qquad \mathrm{\textbf{(C)} \ } 270 \qquad \mathrm{\textbf{(D)} \ }469\qquad \mathrm{\textbf{(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. Note: let $A \geq C$ so that we avoid counting the same permutations and having to subtract them later.


$\textbf{Case$ (Error compiling LaTeX. Unknown error_msg)1$}$ (Error compiling LaTeX. Unknown error_msg): $A+B=C$.


$\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$$ (Error compiling LaTeX. Unknown error_msg)\textbf{Part $2$}$:$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 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 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 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 594 and 3 ways for 484. This leads to$9$cases.

This case has$ (Error compiling LaTeX. Unknown error_msg)18+45+33+21+9=126$subcases.$\textbf{Case $2$}$:$A+B=C+11$.$\textbf{Part $1$}$:$C=0, A+B=11$, this cases results in$209, 308, 407, 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,517,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, 627. There are$6$ways to arrange each of those cases. This leads to$18$cases.

... If we continue this counting, we receive$ (Error compiling LaTeX. Unknown error_msg)16+21+18+15+12+9+6+3=100$subcases.$100+126=\boxed{\textbf{(A) } $226$}$

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

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

We can then multiply by $6$ for each permutation of these multiples. (Yet some multiples do not have six distinct permutations.)

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

Basically, each multiple of $11$ has its own $3$ permutations (say $abc$ has $abc$ $acb$ and $bac$ whereas $cba$ has $cba$ $cab$ and $bca$). We know that each multiple of $11$ has at least $3$ permutations because it cannot have $3$ repeating digits.

Hence we have $243$ permutations without subtracting for overcounting. Now note that we overcounted cases in which we have $0$'s at the start of each number. So, in theory, we could just answer $A$ and then move on.

If we want to solve it, then we continue.

We overcounted cases where the middle digit of the number is $0$ and the last digit is $0$.

Note that we assigned each multiple of $11$ three permutations.

The last digit is $0$ gives $9$ possibilities where we overcounted 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 $\boxed{\textbf{(A) } 226}$.

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 three-digit number in each of the cases.

Solution 4: A Slightly Adjusted Version of Solution 2

$\textbf{WARNING:}$ If you do not feel comfortable looking at a massive amount of casework, please skip the solution.


Recalling the divisibility rule for $11$, if we have a number $ABC$ where $A$, $B$, $C$ are digits, then $11\mid -A+B-C$.

Notice that for any three-digit positive integer $ABC$, $-A+B-C<11$, thus we have 2 possibilities: $-A+B-C=0$ and $-A+B-C=-11$.

$\textbf{Case 1:}$ $-A+B-C=0\Longrightarrow A+C=B$

Subcase $a$: $A\neq B\neq C\neq0$

We have these values for $A+C=B$ \[1+2=3,1+3=4,1+4=5,...,1+8=9\] \[2+3=5,2+4=6,...,2+7=9\] \[3+4=7,3+5=8,3+6=9\] \[4+5=9\] From which we get $7+5+3+1=16$ triples $(A,B,C)$. Counting every permutation, we have $16\cdot3!=96$ possibilities.

Subcase $b$: $A=C$, $A,B,C\neq0$

We have \[1+1=2,2+2=4,3+3=6,4+4=8\] From which we get $4\cdot3=12$ possibilities.

Subcase $c$: $A=B,C=0$

We have \[1+0=1,2+0=2,...,9+0=9\] Since $0$ can't be the hundreds digit, from here we get $9\cdot2=18$ possibilities. Summing up case $1$, we have $96+12+18=126$ possibilities.

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

Subcase $a$: $A\neq B\neq C\neq0$

We have these values for $A+C-B=11$ \[9+8-6=11,9+7-5=11,...9+3-1=11\] \[8+7-4=11,8+6-3=11,8+5-2=11,8+4-1\] \[...\] From which we get $(6+4+2)\cdot3!=72$ possibilities.

Subcase $b$: $A=C$, $A,B,C\neq0$

We have \[9+9=7,8+8-5,7+7-3=11,6+6-1=11\] From which we get $4\cdot3=12$ possibilities.

Subcase $c$: $B=0\Longrightarrow A+C+11$

We have \[9+2=8+3=7+4=6+5=11\] From which we get $2\cdot2\cdot4=16$ possibilities. Summing up case $2$, we have $72+12+16=100$ possibilities.

Adding the $2$ cases, we get a total of $126+100=226$ possibilities. $\boxed{\mathrm{(A)}}$

~ Nafer

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=114044"