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)
m (consistent formatting of answer choices)
 
(135 intermediate revisions by 54 users not shown)
Line 2: Line 2:
 
How many integers between <math>100</math> and <math>999</math>, inclusive, have the property that some permutation of its digits is a multiple of <math>11</math> between <math>100</math> and <math>999?</math> For example, both <math>121</math> and <math>211</math> have this property.
 
How many integers between <math>100</math> and <math>999</math>, inclusive, have the property that some permutation of its digits is a multiple of <math>11</math> between <math>100</math> and <math>999?</math> For example, both <math>121</math> and <math>211</math> have this property.
  
−
<math> \mathrm{(A) \ }226\qquad \mathrm{(B) \ } 243 \qquad \mathrm{(C) \ } 270 \qquad \mathrm{(D) \ }469\qquad \mathrm{(E) \ } 486</math>
+
<math>\textbf{(A) } 226 \qquad \textbf{(B) } 243 \qquad \textbf{(C) } 270 \qquad \textbf{(D) } 469 \qquad \textbf{(E) } 486</math>
  
−
==Solution==
+
==Solution 1==
 +
There are 81 multiples of 11 between <math>100</math> and <math>999</math> inclusive. Some have digits repeated twice, making 3 permutations.
  
−
Let the three-digit number be <math>ACB</math>:
+
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.
  
−
If a number is divisible by 11, then the difference between the sums of alternating digits is a multiple of 11.
+
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 two cases:
+
There are 110, 220, 330 ... 990, yielding 9 extra permutations
−
<math>A+B=C</math>
 
−
<math>A+B=C+11</math>
 
  
−
We now proceed to break down the cases.
+
Also, there are 209, 308, 407...902, yielding 8 more permutations.
  
 +
Now, just subtract these 17 from the total (243) to get 226. <math>\boxed{\textbf{(A) } 226}</math>
  
−
<math>\textbf{Case 1}</math>: <math>A+B=C</math>. This has <math>18+45+33+21+9=126</math> cases.
+
*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:
  
−
<math>\textbf{Part 1}</math>: <math>B=0</math>
+
<math>\textbf{Case 1:}</math> All three digits are the same.
−
<math>A=C</math>, this case results in 110, 220, 330...990. There are two ways to arrange the digits in each of those numbers.
+
By inspection, we find that there are no multiples of <math>11</math> here.
−
<math>2 \cdot 9 = 18</math>
 
  
−
<math>\textbf{Part 2}</math>: <math>B>0</math>
+
<math>\textbf{Case 2:}</math> Two of the digits are the same, and the third is different.
−
<math>B=1, A=C+1</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 ways for the first. This leads to <math>45</math> cases.
 
  
−
<math>\textbf{Part 3}</math>: <math>B=2, A=C+2</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 ways for the first. This leads to <math>33</math> cases.
+
<math>\textbf{Case 2a:}</math>
 +
There are <math>8</math> multiples of <math>11</math> without a zero that have this property:
 +
<math>121</math>, <math>242</math>, <math>363</math>, <math>484</math>, <math>616</math>, <math>737</math>, <math>858</math>, <math>979</math>.
 +
Each contributes <math>3</math> valid permutations, so there are <math>8 \cdot 3 = 24</math> permutations in this subcase.
  
−
<math>\textbf{Part 4}</math>: <math>B=3, A=C+3</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 ways for the first. This leads to <math>21</math> cases.
+
<math>\textbf{Case 2b:}</math>
 +
There are <math>9</math> multiples of <math>11</math> with a zero that have this property:
 +
<math>110</math>, <math>220</math>, <math>330</math>, <math>440</math>, <math>550</math>, <math>660</math>, <math>770</math>, <math>880</math>, <math>990</math>.
 +
Each one contributes <math>2</math> valid permutations (the first digit can't be zero), so there are <math>9 \cdot 2 = 18</math> permutations in this subcase.
  
−
<math>\textbf{Part 5}</math>: <math>B=4, A=C+4</math>, this case results in 484 and 594. There are <math>6</math> ways to arrange the digits in all of those number except the first, and 3 ways ways for the first. This leads to <math>9</math> cases.
+
<math>\textbf{Case 3:}</math> All the digits are different.
 +
Since there are <math>\frac{990-110}{11}+1 = 81</math> multiples of <math>11</math> between <math>100</math> and <math>999</math>, there are <math>81-8-9 = 64</math> multiples of <math>11</math> remaining in this case. However, <math>8</math> of them contain a zero, namely <math>209</math>, <math>308</math>, <math>407</math>, <math>506</math>, <math>605</math>, <math>704</math>, <math>803</math>, and <math>902</math>. Each of those multiples of <math>11</math> contributes <math>2 \cdot 2=4</math> valid permutations, but we overcounted by a factor of <math>2</math>; every permutation of <math>209</math>, for example, is also a permutation of <math>902</math>. Therefore, there are <math>8 \cdot 4 / 2 = 16</math>. Therefore, there are <math>64-8=56</math> remaining multiples of <math>11</math> without a <math>0</math> in this case. Each one contributes <math>3! = 6</math> valid permutations, but once again, we overcounted by a factor of <math>2</math> (note that if a number ABC is a multiple of <math>11</math>, then so is CBA). Therefore, there are <math>56 \cdot 6 / 2 = 168</math> valid permutations in this subcase.
  
 +
Adding up all the permutations from all the cases, we have <math>24+18+16+168 = \boxed{\textbf{(A) } 226}</math>.
  
 +
==Solution 3 ==
  
−
<math>\textbf{Case 2}</math>: <math>A+B=C+11</math>.  
+
We can first overcount and then subtract.
 +
We know that there are <math>81</math> multiples of <math>11</math>.
  
 +
We can then multiply by <math>6</math> for each permutation of these multiples. (Yet some multiples do not have six distinct permutations.)
  
−
<math>\textbf{Part 1}</math>: <math>C=0, A+B=11</math>, this cases results in 209, 308, ...506. There are <math>4</math> ways to arrange each of those cases. This leads to <math>16</math> cases.
+
Now divide by <math>2</math>, because if a number <math>abc</math> with digits <math>a</math>, <math>b</math>, and <math>c</math> is a multiple of <math>11</math>, then <math>cba</math> is also a multiple of <math>11</math> so we have counted the same permutations twice.  
  
−
<math>\textbf{Part 2}</math>: <math>C=1, A+B=12</math>, this cases results in 319, 418, ...616. There are <math>6</math> ways to arrange each of those cases, except the last. This leads to <math>21</math> cases.
+
Basically, each multiple of <math>11</math> has its own <math>3</math> permutations (say <math>abc</math> has <math>abc</math> <math>acb</math> and <math>bac</math> whereas <math>cba</math> has <math>cba</math> <math>cab</math> and <math>bca</math>). We know that each multiple of <math>11</math> has at least <math>3</math> permutations because it cannot have <math>3</math> repeating digits.
  
−
<math>\textbf{Part 3}</math>: <math>C=2, A+B=13</math>, this cases results in 429, 528, ...617. There are <math>6</math> ways to arrange each of those cases. This leads to <math>18</math> cases.
+
Hence we have <math>243</math> permutations without subtracting for overcounting.
 +
Now note that we overcounted cases in which we have <math>0</math>'s at the start of each number. So, in theory, we could just answer <math>A</math> and then move on.
  
−
...
+
If we want to solve it, then we continue.
−
If you continue this counting, you receive <math>16+21+18+15+12+9+6+3=100</math> cases.
 
  
−
<math>100+126=\boxed{(A) 226}</math>
+
We overcounted cases where the middle digit of the number is <math>0</math> and the last digit is <math>0</math>.
 +
 
 +
Note that we assigned each multiple of <math>11</math> three permutations.
 +
 
 +
The last digit is <math>0</math> gives <math>9</math> possibilities where we overcounted by <math>1</math> permutation for each of <math>110, 220, ... , 990</math>.
 +
 
 +
The middle digit is <math>0</math> gives <math>8</math> possibilities where we overcount by <math>1</math>.
 +
<math>605, 704, 803, 902</math> and <math>506, 407, 308, 209</math>
 +
 
 +
Subtracting <math>17</math> gives <math>\boxed{\textbf{(A) } 226}</math>.
 +
 
 +
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 4 (process of elimination on multiple choices) ==
 +
Taken from solution three, we notice that there are a total of <math>81</math> multiples of <math>11</math> between <math>100</math> and <math>999</math>, and each of them have at most <math>6</math> permutation (and thus is a permutations of <math>6</math> numbers), giving us a maximum of <math>486</math> valid numbers.
 +
 
 +
However, if <math>abc</math> can be divided by <math>11</math>, so can <math>cba</math>, which is distinct if <math> c \neq a</math>. And if <math>c = a</math> then <math>abc</math> and <math>cba</math> have the same permutations. Either way, we have doubled counted.
 +
This reduces the number of permutations to <math>486/2 =  243</math>.
 +
 
 +
Furthermore, if <math>a=b</math> or <math>c=0</math> (which turn out to be equivalent conditions! for example <math>220</math>), not all (inverse) permutations are distinct (<math>\mathbf{2}20 = 2\mathbf{2}0</math>) or valid (<math>022</math>). (There are 9 of these.)
 +
 
 +
Similarly, for <math>a0b</math>, not all (inverse) permutations are valid. (There are 8 of these.)
 +
 
 +
As long as you notice at least one example of one of these 3 cases, you may infer that the answer must be smaller than <math>243</math>. This leaves us with only one possible answer: <math>\boxed{\textbf{(A) } 226}</math>.
 +
 
 +
==Video Solution==
 +
Two different variations on solving it.
 +
https://youtu.be/z5KNZEwmrWM
 +
 
 +
https://youtu.be/MBcHwu30MX4
 +
-Video Solution by Richard Rusczyk
 +
 
 +
https://youtu.be/Ly69GHOq9Yw
 +
 
 +
~savannahsolver
  
 
==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}}
 +
 +
[[Category:Intermediate Combinatorics Problems]]

Latest revision as of 16:02, 4 July 2023

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.

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

Solution 1

There are 81 multiples of 11 between $100$ and $999$ 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 $6 \div 2 = 3$ permutations to each multiple.

There are now 81*3 = 243 permutations, but we have overcounted*. Some multiples of 11 have $0$ as a digit. Since $0$ 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. $\boxed{\textbf{(A) } 226}$

  • 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 $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 (process of elimination on multiple choices)

Taken from solution three, we notice that there are a total of $81$ multiples of $11$ between $100$ and $999$, and each of them have at most $6$ permutation (and thus is a permutations of $6$ numbers), giving us a maximum of $486$ valid numbers.

However, if $abc$ can be divided by $11$, so can $cba$, which is distinct if $c \neq a$. And if $c = a$ then $abc$ and $cba$ have the same permutations. Either way, we have doubled counted. This reduces the number of permutations to $486/2 = 243$.

Furthermore, if $a=b$ or $c=0$ (which turn out to be equivalent conditions! for example $220$), not all (inverse) permutations are distinct ($\mathbf{2}20 = 2\mathbf{2}0$) or valid ($022$). (There are 9 of these.)

Similarly, for $a0b$, not all (inverse) permutations are valid. (There are 8 of these.)

As long as you notice at least one example of one of these 3 cases, you may infer that the answer must be smaller than $243$. This leaves us with only one possible answer: $\boxed{\textbf{(A) } 226}$.

Video Solution

Two different variations on solving it. https://youtu.be/z5KNZEwmrWM

https://youtu.be/MBcHwu30MX4 -Video Solution by Richard Rusczyk

https://youtu.be/Ly69GHOq9Yw

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

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