Difference between revisions of "2017 AMC 10A Problems/Problem 25"

m (Video Solution)
(Solution 1)
(20 intermediate revisions by 7 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. Therefore, assign 3 permutations to each multiple.
+
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 zero, and we must subtract a permutation for each.  
+
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), getting 226. <math>\boxed{\textbf{(A) } 226}</math>
+
Now, just subtract these 17 from the total (243) to get 226. <math>\boxed{\textbf{(A) } 226}</math>
  
*Note: If short on time, note that 226 is the only answer choice less than 243, and therefore is the only feasible answer.  
+
*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===
+
==Solution 2==
 
 
Let the three-digit number be <math>ACB</math>:
 
 
 
If a number is divisible by <math>11</math>, then the difference between the sums of alternating digits is a multiple of <math>11</math>.
 
 
 
There are two cases:
 
<math>A+B=C</math> and <math>A+B=C+11</math>
 
 
 
We now proceed to break down the cases. Note: let <math>A \geq C</math> so that we avoid counting the same permutations and having to subtract them later.
 
 
 
 
 
<math>\textbf{Case 1}</math>: <math>A+B=C</math>.
 
 
 
 
 
 
 
<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>\textbf{Part 2}</math>:
 
<math>B=1, A+1=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 <math>3</math> 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 <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 <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 <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.
 
 
 
 
 
 
 
<math>\textbf{Case 2}</math>: <math>A+B=C+11</math>.
 
 
 
 
 
<math>\textbf{Part 1}</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 <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 <math>429, 528, 627</math>. 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.
 
 
 
<math>100+126=\boxed{\textbf{(A) } 226}</math>
 
 
 
==Solution 3==
 
  
 
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 4 ==
+
==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 5: A Slightly Adjusted Version of Solution 2 ==
+
== Solution 4 (1 but quicker) ==
 
 
 
 
<math>\textbf{WARNING:}</math> If you do not feel comfortable looking at a massive amount of casework, please skip the solution.
 
 
 
 
 
Recalling the divisibility rule for <math>11</math>, if we have a number <math>ABC</math> where <math>A</math>, <math>B</math>, <math>C</math> are digits, then <math>11\mid -A+B-C</math>.
 
 
 
Notice that for any three-digit positive integer <math>ABC</math>, <math>-A+B-C<11</math>, thus we have 2 possibilities: <math>-A+B-C=0</math> and <math>-A+B-C=-11</math>.
 
 
 
<math>\textbf{Case 1:}</math> <math>-A+B-C=0\Longrightarrow A+C=B</math>
 
 
 
Subcase <math>a</math>: <math>A\neq B\neq C\neq0</math>
 
 
 
We have these values for <math>A+C=B</math>
 
<cmath>1+2=3,1+3=4,1+4=5,...,1+8=9</cmath>
 
<cmath>2+3=5,2+4=6,...,2+7=9</cmath>
 
<cmath>3+4=7,3+5=8,3+6=9</cmath>
 
<cmath>4+5=9</cmath>
 
From which we get <math>7+5+3+1=16</math> triples <math>(A,B,C)</math>. Counting every permutation, we have <math>16\cdot3!=96</math> possibilities.
 
 
 
Subcase <math>b</math>: <math>A=C</math>, <math>A,B,C\neq0</math>
 
 
 
We have
 
<cmath>1+1=2,2+2=4,3+3=6,4+4=8</cmath>
 
From which we get <math>4\cdot3=12</math> possibilities.
 
 
 
Subcase <math>c</math>: <math>A=B,C=0</math>
 
 
 
We have
 
<cmath>1+0=1,2+0=2,...,9+0=9</cmath>
 
Since <math>0</math> can't be the hundreds digit, from here we get <math>9\cdot2=18</math> possibilities. Summing up case <math>1</math>, we have <math>96+12+18=126</math> possibilities.
 
 
 
<math>\textbf{Case 2:}</math> <math>-A+B-C=-11\Longrightarrow A+C-B=11</math>
 
  
Subcase <math>a</math>: <math>A\neq B\neq C\neq0</math>
+
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>.
  
We have these values for <math>A+C-B=11</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>.
<cmath>9+8-6=11,9+7-5=11,...9+3-1=11</cmath>
 
<cmath>8+7-4=11,8+6-3=11,8+5-2=11,8+4-1</cmath>
 
<cmath>...</cmath>
 
From which we get <math>(6+4+2)\cdot3!=72</math> possibilities.
 
  
Subcase <math>b</math>: <math>A=C</math>, <math>A,B,C\neq0</math>
+
-¢
 
 
We have
 
<cmath>9+9=7,8+8-5,7+7-3=11,6+6-1=11</cmath>
 
From which we get <math>4\cdot3=12</math> possibilities.
 
 
 
Subcase <math>c</math>: <math>B=0\Longrightarrow A+C+11</math>
 
 
 
We have
 
<cmath>9+2=8+3=7+4=6+5=11</cmath>
 
From which we get <math>2\cdot2\cdot4=16</math> possibilities. Summing up case <math>2</math>, we have <math>72+12+16=100</math> possibilities.
 
 
 
Adding the <math>2</math> cases, we get a total of <math>126+100=226</math> possibilities. <math>\boxed{\mathrm{(A)}}</math>
 
 
 
~ Nafer
 
  
 
==Video Solution==
 
==Video Solution==
Line 183: Line 86:
 
https://youtu.be/MBcHwu30MX4
 
https://youtu.be/MBcHwu30MX4
 
-Video Solution by Richard Rusczyk
 
-Video Solution by Richard Rusczyk
 +
 +
https://youtu.be/Ly69GHOq9Yw
 +
 +
~savannahsolver
  
 
==See Also==
 
==See Also==

Revision as of 17:16, 24 July 2021

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

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}$

  • 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 $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 (1 but quicker)

The smallest multiple of $11$ above $100$ is $110 = 11 \cdot 10$, while the largest multiple of $11$ less than $999$ is $990 = 11 \cdot 90$. This means there are $90 - 10 + 1 = 81$ multiples of $11$ between $100$ and $999$.

As there are $3$ permutations for each multiple, we have $81 * 3 = 243$. However, we have overcounted, as numbers like $099$ shouldn't be counted. Looking at the answer choices, we notice there is only one that is less than $243$, and so we have our answer as $\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 (ProblemsAnswer KeyResources)
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