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 4 (1 but quicker))
m (consistent formatting of answer choices)
 
(9 intermediate revisions by 3 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{\textbf{(A)} \ }226\qquad \mathrm{\textbf{(B)} \ } 243 \qquad \mathrm{\textbf{(C)} \ } 270 \qquad \mathrm{\textbf{(D)} \ }469\qquad \mathrm{\textbf{(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 1==
 
==Solution 1==
Line 72: 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 (Bashier version of Solution 2)==
+
==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.
  
−
Basically, we see that we just have to list out <math>81</math> numbers that satisfy the condition of divisible by <math>11</math> so we can basically list out the possible numbers and group them out by the hundred's digit. While, listing out, we notice that some of the numbers can be removed from the count because some numbers would have the same permutations, when we notice this we can remove these.
+
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>.  
  
−
Using the remaining numbers, we just have to count the number of ways to arrange each of the possible cases.
+
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.)
  
−
These cases would be:
+
Similarly, for <math>a0b</math>, not all (inverse) permutations are valid. (There are 8 of these.)
  
−
Case <math>1</math>: all distinct digits without <math>0</math>'s
+
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>.
−
 
 
−
There are <math>28</math> from the remaining list that satisfy this. As each has <math>6</math> permutations we get <math>28 \times 6 = 168</math> ways.
 
−
 
 
−
Case <math>2</math>: All distinct digits, but with <math>0</math>:
 
−
 
 
−
There are <math>4</math> numbers from our remaining list, and as the digits are distinct, there are <math>6</math> ways - <math>2</math> ways = <math>4</math> ways because we've to remove the permutations of when the first digit is <math>0</math> which is <math>2</math> ways. This gives <math>4\times4=16</math> ways.
 
−
 
 
−
Case <math>3</math>: <math>1</math> common digit, <math>2</math> different digits, no <math>0</math>:
 
−
 
 
−
There are <math>8</math> numbers from our remaining list, and as there are 2 common digits, we get the number of ways to arrange as <math>\dfrac{3!}{2!}=3</math> ways. This gives <math>3\times8=24</math> ways.
 
−
 
 
−
Case <math>4</math>: <math>1</math> common digit, <math>2</math> different digits, the other digit is <math>0</math>:
 
−
 
 
−
There are <math>9</math> numbers from our remaining list that work and there are <math>3-1=2</math> ways, to not include <math>0</math> as first digit. This gives <math>2\times9=18</math> ways.
 
−
 
 
−
Adding the cases up gives us <math>168+16+24+18=\boxed{\textbf{(A) } 226}</math>
 
−
 
 
−
Note: Solution <math>2</math> is a much more efficient version of this solution, so if you are desperate and can't think of anything else, a solution like this would be smart
 
−
 
 
−
~Batmanstark
 
  
 
==Video Solution==
 
==Video Solution==

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"