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 "2018 AMC 12B Problems/Problem 15"
 
(28 intermediate revisions by 15 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
How many odd positive 3-digit integers are divisible by 3 but do not contain the digit 3?
+
How many odd positive <math>3</math>-digit integers are divisible by <math>3</math> but do not contain the digit <math>3</math>?
  
 
<math>\textbf{(A) } 96 \qquad \textbf{(B) } 97 \qquad \textbf{(C) } 98 \qquad \textbf{(D) } 102 \qquad \textbf{(E) } 120 </math>
 
<math>\textbf{(A) } 96 \qquad \textbf{(B) } 97 \qquad \textbf{(C) } 98 \qquad \textbf{(D) } 102 \qquad \textbf{(E) } 120 </math>
  
−
== Solution 1 (For Dummies) ==
+
== Solution 1 ==
−
Analyze that the three-digit integers divisible by <math>3</math> start from <math>102</math>. In the <math>200</math>'s, it starts from <math>201</math>. In the <math>300</math>'s, it starts from <math>300</math>. We see that the units digits is <math>0, 1, </math> and <math>2.</math>
+
Let <math>\underline{ABC}</math> be one such odd positive <math>3</math>-digit integer with hundreds digit <math>A,</math> tens digit <math>B,</math> and ones digit <math>C.</math> Since <math>\underline{ABC}\equiv0\pmod3,</math> we need <math>A+B+C\equiv0\pmod3</math> by the divisibility rule for <math>3.</math>
  
−
Write out the 1- and 2-digit multiples of <math>3</math> starting from <math>0, 1,</math> and <math>2.</math> Count up the ones that meet the conditions. Then, add up and multiply by <math>3</math>, since there are three sets of three from <math>1</math> to <math>9.</math> Then, subtract the amount that started from <math>0</math>, since the <math>300</math>'s all contain the digit <math>3</math>.
+
As <math>A\in\{1,2,4,5,6,7,8,9\}</math> and <math>C\in\{1,5,7,9\},</math> there are <math>8</math> possibilities for <math>A</math> and <math>4</math> possibilities for <math>C.</math> Note that each ordered pair <math>(A,C)</math> determines the value of <math>B</math> modulo <math>3,</math> so <math>B</math> can be any element in one of the sets <math>\{0,6,9\},\{1,4,7\},</math> or <math>\{2,5,8\}.</math> We conclude that there are always <math>3</math> possibilities for <math>B.</math>
  
−
We get: <cmath>3(12+12+12)-12.</cmath>
+
By the Multiplication Principle, the answer is <math>8\cdot4\cdot3=\boxed{\textbf{(A) } 96}.</math>
  
−
This gives us: <cmath>\boxed{\textbf{(A) } 96}.</cmath>
+
~Plasma_Vortex ~MRENTHUSIASM
  
−
== Solution 2==
+
== Solution 2 ==
 +
Let <math>\underline{ABC}</math> be one such odd positive <math>3</math>-digit integer with hundreds digit <math>A,</math> tens digit <math>B,</math> and ones digit <math>C.</math> Since <math>\underline{ABC}\equiv0\pmod3,</math> we need <math>A+B+C\equiv0\pmod3</math> by the divisibility rule for <math>3.</math>
  
−
There are <math>4</math> choices for the last digit (<math>1, 5, 7, 9</math>), and <math>8</math> choices for the first digit (exclude <math>0</math>). We know what the second digit mod  <math>3</math> is, so there are <math>3</math> choices for it (pick from one of the sets <math>\{0, 6, 9\},\{1, 4, 7\}, \{2, 5, 8\}</math>). The answer is <math>4\cdot 8 \cdot 3 = \boxed{96}</math> (Plasma_Vortex)
+
As <math>A\in\{1,2,4,5,6,7,8,9\},B\in\{0,1,2,4,5,6,7,8,9\},</math> and <math>C\in\{1,5,7,9\},</math> note that:
 +
<ol style="margin-left: 1.5em;">
 +
  <li>There are <math>2</math> possibilities for <math>A\equiv0\pmod3,</math> namely <math>A=6,9.</math> <p>
 +
There are <math>3</math> possibilities for <math>A\equiv1\pmod3,</math> namely <math>A=1,4,7.</math> <p>
 +
There are <math>3</math> possibilities for <math>A\equiv2\pmod3,</math> namely <math>A=2,5,8.</math> <p>
 +
</li>
 +
  <li>There are <math>3</math> possibilities for <math>B\equiv0\pmod3,</math> namely <math>B=0,6,9.</math> <p>
 +
There are <math>3</math> possibilities for <math>B\equiv1\pmod3,</math> namely <math>B=1,4,7.</math> <p>
 +
There are <math>3</math> possibilities for <math>B\equiv2\pmod3,</math> namely <math>B=2,5,8.</math> <p>
 +
</li>
 +
  <li>There are <math>1</math> possibility for <math>C\equiv0\pmod3,</math> namely <math>C=9.</math> <p>
 +
There are <math>2</math> possibilities for <math>C\equiv1\pmod3,</math> namely <math>C=1,7.</math> <p>
 +
There are <math>1</math> possibility for <math>C\equiv2\pmod3,</math> namely <math>C=5.</math> <p>
 +
</li>
 +
</ol>
 +
We apply casework to <math>A+B+C\equiv0\pmod3:</math>
 +
<cmath>\begin{array}{c|c|c||l}
 +
& & & \\ [-2.5ex]
 +
\boldsymbol{A\operatorname{mod}3} & \boldsymbol{B\operatorname{mod}3} & \boldsymbol{C\operatorname{mod}3} & \multicolumn{1}{c}{\textbf{Count}} \\ [0.5ex]
 +
\hline
 +
& & &  \\ [-2ex]
 +
0 & 0 & 0 & 2\cdot3\cdot1=6 \\
 +
0 & 1 & 2 & 2\cdot3\cdot1=6 \\
 +
0 & 2 & 1 & 2\cdot3\cdot2=12 \\
 +
1 & 0 & 2 & 3\cdot3\cdot1=9 \\
 +
1 & 1 & 1 & 3\cdot3\cdot2=18 \\
 +
1 & 2 & 0 & 3\cdot3\cdot1=9 \\
 +
2 & 0 & 1 & 3\cdot3\cdot2=18 \\
 +
2 & 1 & 0 & 3\cdot3\cdot1=9 \\
 +
2 & 2 & 2 & 3\cdot3\cdot1=9
 +
\end{array}</cmath>
 +
Together, the answer is <math>6+6+12+9+18+9+18+9+9=\boxed{\textbf{(A) } 96}.</math>
 +
 
 +
~MRENTHUSIASM
 +
 
 +
== Solution 3 ==
 +
Analyze that the three-digit integers divisible by <math>3</math> start from <math>102.</math> In the <math>200</math>'s, it starts from <math>201.</math> In the <math>300</math>'s, it starts from <math>300.</math> We see that the units digits is <math>0, 1, </math> and <math>2.</math>
 +
 
 +
Write out the <math>1</math>- and <math>2</math>-digit multiples of <math>3</math> starting from <math>0, 1,</math> and <math>2.</math> Count up the ones that meet the conditions. Then, add up and multiply by <math>3,</math> since there are three sets of three from <math>1</math> to <math>9.</math> Then, subtract the amount that started from <math>0,</math> since the <math>300</math>'s ll contain the digit <math>3.</math>
 +
 
 +
Together, the answer is <math>3(12+12+12)-12=\boxed{\textbf{(A) } 96}.</math>
 +
 
 +
== Solution 4 ==
 +
 
 +
Consider the number of <math>2</math>-digit numbers that do not contain the digit <math>3,</math> which is <math>90-18=72.</math> For any of these <math>2</math>-digit numbers, we can append <math>1,5,7,</math> or <math>9</math> to reach a desirable <math>3</math>-digit number. However, we have <math>7 \equiv 1\pmod{3},</math> and thus we need to count any <math>2</math>-digit number <math>\equiv 2\pmod{3}</math> twice. There are <math>(98-11)/3+1=30</math> total such numbers that have remainder <math>2,</math> but <math>6</math> of them <math>(23,32,35,38,53,83)</math> contain <math>3,</math> so the number we want is <math>30-6=24.</math> Therefore, the final answer is <math>72+24= \boxed{\textbf{(A) } 96}.</math>
 +
 
 +
== Solution 5 ==
 +
We need to take care of all restrictions. Ranging from <math>101</math> to <math>999,</math> there are <math>450</math> odd <math>3</math>-digit numbers. Exactly <math>\frac{1}{3}</math> of these numbers are divisible by <math>3,</math> which is <math>450\cdot\frac{1}{3}=150.</math> Of these <math>150</math> numbers, <math>\frac{4}{5}</math> <math>\textbf{do not}</math> have <math>3</math> in their ones (units) digit, <math>\frac{9}{10}</math> <math>\textbf{do not}</math> have <math>3</math> in their tens digit, and <math>\frac{8}{9}</math> <math>\textbf{do not}</math> have <math>3</math> in their hundreds digit. Thus, the total number of <math>3</math>-digit integers is <cmath>900\cdot\frac{1}{2}\cdot\frac{1}{3}\cdot\frac{4}{5}\cdot\frac{9}{10}\cdot\frac{8}{9}=\boxed{\textbf{(A) } 96}.</cmath>
 +
 
 +
~mathpro12345
 +
 
 +
==Solution 6==
 +
 
 +
We will start with the numbers that could work. This numbers include _ _ <math>1</math>, _ _ <math>5</math>, _ _ <math>7</math>, _ _ <math>9</math>. Let's work case by case.
 +
 
 +
Case <math>1</math>: _ _ <math>1</math>: The two blanks could be any number that is <math>2</math> mod <math>3</math> that does not include <math>3</math>. We have <math>24</math> cases for this case (we could count every case).
 +
 
 +
Case <math>2</math>: _ _ <math>5</math>: The <math>2</math> blanks could be any number that is <math>1</math> mod <math>3</math> that does not include <math>3</math>. But we could see that this case has exactly the same solutions to case <math>1</math> because we have a <math>1-1</math> correspondence. We can do the exact same for case <math>3</math>.
 +
 
 +
Cases <math>4</math>: _ _ <math>9</math>: We need the blanks to be a multiple of <math>3</math>, but does not contain 3. We have <math>(12, 15, 18, 21, 24, 27, 42, 45, 48, 51, 54, 57, 60, 66, 69, 72, 75, 78, 81, 84, 87, 90, 96, 99)</math> which also contains <math>24</math> numbers. Therefore, we have <math>24 \cdot 4</math> which is equal to <math>\boxed{\textbf{(A) } 96}.</math>
 +
 
 +
~Arcticturn
 +
 
 +
==Solution 7==
 +
 
 +
This problem is solvable by inclusion exclusion principle. There are <math>\frac{999-105}{6} + 1 = 150</math> odd <math>3</math>-digit numbers divisible by <math>3</math>. We consider the number of <math>3</math>-digit numbers divisible by <math>3</math> that contain either <math>1, 2</math> or <math>3</math> digits of <math>3</math>.
 +
 
 +
For <math>\underline{AB3}</math>, <math>AB</math> is any <math>2</math>-digit number divisible by <math>3</math>, which gives us <math>\frac{99-12}{3} + 1 = 30</math>. For <math>\underline{A3B}</math>, for each odd <math>B</math>, we have <math>3</math> values of <math>A</math> that give a valid case, thus we have <math>5(3) = 15</math> cases. For <math>\underline{3AB}</math>, we also have <math>15</math> cases, but when <math>B=3, 9</math>, <math>A</math> can equal <math>0</math>, so we have <math>17</math> cases.
 +
 
 +
For <math>\underline{A33}</math>, we have <math>3</math> cases. For <math>\underline{3A3}</math>, we have <math>4</math> cases. For <math>\underline{33A}</math>, we have <math>2</math> cases. Finally, there is just one case for <math>\underline{333}</math>.
 +
 
 +
By inclusion exclusion principle, we get <math>150 - 30 - 15 - 17 + 3 + 4 + 2 - 1 = \boxed{\textbf{(A) } 96}</math> numbers.
 +
 
 +
~Zeric
 +
 
 +
== Video Solution by Omega Learn ==
 +
https://youtu.be/mgEZOXgIZXs?t=448
 +
 
 +
~ pi_is_3.14
 +
 
 +
==Video Solution by WhyMath==
 +
https://youtu.be/vdJFrAq0NDY
 +
 
 +
~savannahsolver
  
 
==See Also==
 
==See Also==
Line 21: Line 105:
 
{{AMC12 box|year=2018|ab=B|num-b=14|num-a=16}}
 
{{AMC12 box|year=2018|ab=B|num-b=14|num-a=16}}
 
{{MAA Notice}}
 
{{MAA Notice}}
 +
 +
[[Category:Introductory Combinatorics Problems]]
 +
[[Category:Introductory Number Theory Problems]]

Latest revision as of 07:19, 30 May 2023

Problem

How many odd positive $3$-digit integers are divisible by $3$ but do not contain the digit $3$?

$\textbf{(A) } 96 \qquad \textbf{(B) } 97 \qquad \textbf{(C) } 98 \qquad \textbf{(D) } 102 \qquad \textbf{(E) } 120$

Solution 1

Let $\underline{ABC}$ be one such odd positive $3$-digit integer with hundreds digit $A,$ tens digit $B,$ and ones digit $C.$ Since $\underline{ABC}\equiv0\pmod3,$ we need $A+B+C\equiv0\pmod3$ by the divisibility rule for $3.$

As $A\in\{1,2,4,5,6,7,8,9\}$ and $C\in\{1,5,7,9\},$ there are $8$ possibilities for $A$ and $4$ possibilities for $C.$ Note that each ordered pair $(A,C)$ determines the value of $B$ modulo $3,$ so $B$ can be any element in one of the sets $\{0,6,9\},\{1,4,7\},$ or $\{2,5,8\}.$ We conclude that there are always $3$ possibilities for $B.$

By the Multiplication Principle, the answer is $8\cdot4\cdot3=\boxed{\textbf{(A) } 96}.$

~Plasma_Vortex ~MRENTHUSIASM

Solution 2

Let $\underline{ABC}$ be one such odd positive $3$-digit integer with hundreds digit $A,$ tens digit $B,$ and ones digit $C.$ Since $\underline{ABC}\equiv0\pmod3,$ we need $A+B+C\equiv0\pmod3$ by the divisibility rule for $3.$

As $A\in\{1,2,4,5,6,7,8,9\},B\in\{0,1,2,4,5,6,7,8,9\},$ and $C\in\{1,5,7,9\},$ note that:

  1. There are $2$ possibilities for $A\equiv0\pmod3,$ namely $A=6,9.$

    There are $3$ possibilities for $A\equiv1\pmod3,$ namely $A=1,4,7.$

    There are $3$ possibilities for $A\equiv2\pmod3,$ namely $A=2,5,8.$

  2. There are $3$ possibilities for $B\equiv0\pmod3,$ namely $B=0,6,9.$

    There are $3$ possibilities for $B\equiv1\pmod3,$ namely $B=1,4,7.$

    There are $3$ possibilities for $B\equiv2\pmod3,$ namely $B=2,5,8.$

  3. There are $1$ possibility for $C\equiv0\pmod3,$ namely $C=9.$

    There are $2$ possibilities for $C\equiv1\pmod3,$ namely $C=1,7.$

    There are $1$ possibility for $C\equiv2\pmod3,$ namely $C=5.$

We apply casework to $A+B+C\equiv0\pmod3:$ \[\begin{array}{c|c|c||l} & & & \\ [-2.5ex] \boldsymbol{A\operatorname{mod}3} & \boldsymbol{B\operatorname{mod}3} & \boldsymbol{C\operatorname{mod}3} & \multicolumn{1}{c}{\textbf{Count}} \\ [0.5ex] \hline & & & \\ [-2ex] 0 & 0 & 0 & 2\cdot3\cdot1=6 \\ 0 & 1 & 2 & 2\cdot3\cdot1=6 \\ 0 & 2 & 1 & 2\cdot3\cdot2=12 \\ 1 & 0 & 2 & 3\cdot3\cdot1=9 \\ 1 & 1 & 1 & 3\cdot3\cdot2=18 \\ 1 & 2 & 0 & 3\cdot3\cdot1=9 \\ 2 & 0 & 1 & 3\cdot3\cdot2=18 \\ 2 & 1 & 0 & 3\cdot3\cdot1=9 \\ 2 & 2 & 2 & 3\cdot3\cdot1=9 \end{array}\] Together, the answer is $6+6+12+9+18+9+18+9+9=\boxed{\textbf{(A) } 96}.$

~MRENTHUSIASM

Solution 3

Analyze that the three-digit integers divisible by $3$ start from $102.$ In the $200$'s, it starts from $201.$ In the $300$'s, it starts from $300.$ We see that the units digits is $0, 1,$ and $2.$

Write out the $1$- and $2$-digit multiples of $3$ starting from $0, 1,$ and $2.$ Count up the ones that meet the conditions. Then, add up and multiply by $3,$ since there are three sets of three from $1$ to $9.$ Then, subtract the amount that started from $0,$ since the $300$'s ll contain the digit $3.$

Together, the answer is $3(12+12+12)-12=\boxed{\textbf{(A) } 96}.$

Solution 4

Consider the number of $2$-digit numbers that do not contain the digit $3,$ which is $90-18=72.$ For any of these $2$-digit numbers, we can append $1,5,7,$ or $9$ to reach a desirable $3$-digit number. However, we have $7 \equiv 1\pmod{3},$ and thus we need to count any $2$-digit number $\equiv 2\pmod{3}$ twice. There are $(98-11)/3+1=30$ total such numbers that have remainder $2,$ but $6$ of them $(23,32,35,38,53,83)$ contain $3,$ so the number we want is $30-6=24.$ Therefore, the final answer is $72+24= \boxed{\textbf{(A) } 96}.$

Solution 5

We need to take care of all restrictions. Ranging from $101$ to $999,$ there are $450$ odd $3$-digit numbers. Exactly $\frac{1}{3}$ of these numbers are divisible by $3,$ which is $450\cdot\frac{1}{3}=150.$ Of these $150$ numbers, $\frac{4}{5}$ $\textbf{do not}$ have $3$ in their ones (units) digit, $\frac{9}{10}$ $\textbf{do not}$ have $3$ in their tens digit, and $\frac{8}{9}$ $\textbf{do not}$ have $3$ in their hundreds digit. Thus, the total number of $3$-digit integers is \[900\cdot\frac{1}{2}\cdot\frac{1}{3}\cdot\frac{4}{5}\cdot\frac{9}{10}\cdot\frac{8}{9}=\boxed{\textbf{(A) } 96}.\]

~mathpro12345

Solution 6

We will start with the numbers that could work. This numbers include _ _ $1$, _ _ $5$, _ _ $7$, _ _ $9$. Let's work case by case.

Case $1$: _ _ $1$: The two blanks could be any number that is $2$ mod $3$ that does not include $3$. We have $24$ cases for this case (we could count every case).

Case $2$: _ _ $5$: The $2$ blanks could be any number that is $1$ mod $3$ that does not include $3$. But we could see that this case has exactly the same solutions to case $1$ because we have a $1-1$ correspondence. We can do the exact same for case $3$.

Cases $4$: _ _ $9$: We need the blanks to be a multiple of $3$, but does not contain 3. We have $(12, 15, 18, 21, 24, 27, 42, 45, 48, 51, 54, 57, 60, 66, 69, 72, 75, 78, 81, 84, 87, 90, 96, 99)$ which also contains $24$ numbers. Therefore, we have $24 \cdot 4$ which is equal to $\boxed{\textbf{(A) } 96}.$

~Arcticturn

Solution 7

This problem is solvable by inclusion exclusion principle. There are $\frac{999-105}{6} + 1 = 150$ odd $3$-digit numbers divisible by $3$. We consider the number of $3$-digit numbers divisible by $3$ that contain either $1, 2$ or $3$ digits of $3$.

For $\underline{AB3}$, $AB$ is any $2$-digit number divisible by $3$, which gives us $\frac{99-12}{3} + 1 = 30$. For $\underline{A3B}$, for each odd $B$, we have $3$ values of $A$ that give a valid case, thus we have $5(3) = 15$ cases. For $\underline{3AB}$, we also have $15$ cases, but when $B=3, 9$, $A$ can equal $0$, so we have $17$ cases.

For $\underline{A33}$, we have $3$ cases. For $\underline{3A3}$, we have $4$ cases. For $\underline{33A}$, we have $2$ cases. Finally, there is just one case for $\underline{333}$.

By inclusion exclusion principle, we get $150 - 30 - 15 - 17 + 3 + 4 + 2 - 1 = \boxed{\textbf{(A) } 96}$ numbers.

~Zeric

Video Solution by Omega Learn

https://youtu.be/mgEZOXgIZXs?t=448

~ pi_is_3.14

Video Solution by WhyMath

https://youtu.be/vdJFrAq0NDY

~savannahsolver

See Also

2018 AMC 12B (Problems • Answer Key • Resources)
Preceded by
Problem 14 		Followed by
Problem 16
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 12 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=2018_AMC_12B_Problems/Problem_15&oldid=193710"