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 "2001 AMC 12 Problems/Problem 12"

(→‎Solution)
(→‎Solutions)
 
(32 intermediate revisions by 13 users not shown)
Line 6: Line 6:
  
 
<math>
 
<math>
−
\text{(A) }768
+
\textbf{(A) }768
 
\qquad
 
\qquad
−
\text{(B) }801
+
\textbf{(B) }801
 
\qquad
 
\qquad
−
\text{(C) }934
+
\textbf{(C) }934
 
\qquad
 
\qquad
−
\text{(D) }1067
+
\textbf{(D) }1067
 
\qquad
 
\qquad
−
\text{(E) }1167
+
\textbf{(E) }1167
 
</math>
 
</math>
  
−
== Solution 1==
+
==Solutions==
 +
=== Solution 1===
  
 
Out of the numbers <math>1</math> to <math>12</math> four are divisible by <math>3</math> and three by <math>4</math>, counting <math>12</math> twice.
 
Out of the numbers <math>1</math> to <math>12</math> four are divisible by <math>3</math> and three by <math>4</math>, counting <math>12</math> twice.
Line 30: Line 31:
 
Again, the same is obviously true for the set <math>\{60k+1,\dots,60k+60\}</math> for any positive integer <math>k</math>.
 
Again, the same is obviously true for the set <math>\{60k+1,\dots,60k+60\}</math> for any positive integer <math>k</math>.
  
−
We have <math>1980/60 = 33</math>, hence there are <math>24\cdot 33 = 792</math> good numbers among the numbers <math>1</math> to <math>1980</math>. At this point we already know that the only answer that is still possible is <math>\boxed{\text{(B)}}</math>, as we only have <math>20</math> numbers left.
+
We have <math>1980/60 = 33</math>, hence there are <math>24\cdot 33 = 792</math> good numbers among the numbers <math>1</math> to <math>1980</math>. At this point we already know that the only answer that is still possible is <math>\boxed{\textbf{(B)}}</math>, as we only have <math>20</math> numbers left.
  
−
By examining the remaining <math>20</math> by hand we can easily find out that exactly <math>9</math> of them match all the criteria, giving us <math>792+9=\boxed{801}</math> good numbers.
+
By examining the remaining <math>20</math> by hand we can easily find out that exactly <math>9</math> of them match all the criteria, giving us <math>792+9=\boxed{\textbf{(B) }801}</math> good numbers.
 
This is correct.
 
This is correct.
 +
 
===Solution 2===
 
===Solution 2===
−
We can solve this problem by finding the cases where the number is divisible by <math>3</math> or <math>4</math>, then subtract from the cases where none of those cases divide <math>5</math>. To solve the ways the numbers divide <math>3</math> or <math>4</math> we find the cases where a number is divisible by <math>3</math> and <math>4</math> as separate cases. We apply the floor function to every case to get <math>\lfloor \frac{2001}{3} \rfloor</math>, <math>\lfloor \frac{2001}{4} \rfloor</math>, and <math>\lfloor \frac{2001}{12} \rfloor</math>. The first two floor functions were for calculating the number of individual cases for <math>3</math> and <math>4</math>. The third case was to find any overlapping numbers. The numbers were <math>667</math>, <math>500</math>, and <math>166</math>, respectively. We add the first two terms and subtract the third to get <math>1001</math>. The first case is finished.
+
We can solve this problem by finding the cases where the number is divisible by <math>3</math> or <math>4</math>, then subtract from the cases where none of those cases divide <math>5</math>. To solve the ways the numbers divide <math>3</math> or <math>4</math> we find the cases where a number is divisible by <math>3</math> and <math>4</math> as separate cases. We apply the floor function to every case to get <math>\left\lfloor \frac{2001}{3} \right\rfloor</math>, <math>\left\lfloor \frac{2001}{4} \right\rfloor</math>, and <math>\left\lfloor \frac{2001}{12} \right\rfloor</math>. The first two floor functions were for calculating the number of individual cases for <math>3</math> and <math>4</math>. The third case was to find any overlapping numbers. The numbers were <math>667</math>, <math>500</math>, and <math>166</math>, respectively. We add the first two terms and subtract the third to get <math>1001</math>. The first case is finished.
 +
 
 +
The second case is more or less the same, except we are applying <math>3</math> and <math>4</math> to <math>5</math>. We must find the cases where the first case over counts multiples of five. Utilizing the floor function again on the fractions <math>\left\lfloor \frac{2001}{3\cdot5} \right\rfloor</math>, <math>\left\lfloor \frac{2001}{4\cdot5} \right\rfloor</math>, and <math>\left\lfloor \frac{2001}{3\cdot4\cdot5} \right\rfloor</math> yields the numbers <math>133</math>, <math>100</math>, and <math>33</math>. The first two numbers counted all the numbers that were multiples of either four with five or three with five less than <math>2001</math>. The third counted the overlapping cases, which we must subtract from the sum of the first two. We do this to reach <math>200</math>. Subtracting this number from the original <math>1001</math> numbers procures <math>\boxed{\textbf{(B)}\ 801}</math>.
 +
 
 +
===Solution 3===
 +
First find the number of such integers between 1 and 2000 (inclusive) and then add one to this result because 2001 is a multiple of <math>3</math>.
 +
 
 +
There are <math>\frac45\cdot2000=1600</math> numbers that are not multiples of <math>5</math>.  <math>\frac23\cdot\frac34\cdot1600=800</math> are not multiples of <math>3</math> or <math>4</math>, so <math>800</math> numbers are.  <math>800+1=\boxed{\textbf{(B)}\ 801}</math>
 +
 
 +
===Solution 4===
 +
Take a good-sized sample of consecutive integers; for example, the first <math>25</math> positive integers. Determine that the numbers <math>3, 4, 6, 8, 9, 12, 16, 18, 21,</math> and <math>24</math> exhibit the properties given in the question. <math>25</math> is a divisor of <math>2000</math>, so there are <math>\frac{10}{25}\cdot2000=800</math> numbers satisfying the given conditions between <math>1</math> and <math>2000</math>. Since <math>2001</math> is a multiple of <math>3</math>, add <math>1</math> to <math>800</math> to get <math>800+1=\boxed{\textbf{(B)}\ 801}</math>.
 +
 
 +
~ mathmagical
 +
 
 +
===Solution 5===
 +
By PIE, there are <math>1001</math> numbers that are multiples of <math>3</math> or <math>4</math> and less than or equal to <math>2001</math>. <math>80\%</math> of them will not be divisible by <math>5</math>, and by far the closest number to <math>80\%</math> of <math>1001</math> is <math>\boxed{\textbf{(B)}\ 801}</math>.
 +
 
 +
~ Fasolinka
 +
 
 +
=== Solution 5===
 +
Similar to some of the above solutions.
 +
We can divide <math>2001</math> by <math>3</math> and <math>4</math> to find the number of integers divisible by <math>3</math> and <math>4</math>. Hence, we find that there are <math>667</math> numbers less than <math>2001</math> that are divisible by <math>3</math>, and <math>500</math> numbers that are divisible by <math>4</math>. However, we will need to subtract the number of multiples of <math>15</math> from 667 and that of <math>20</math> from <math>500</math>, since they're also divisible by 5 which we don't want. There are <math>133</math> + <math>100</math> = <math>233</math> such numbers. Note that during this process, we've subtracted the multiples of <math>60</math> twice because they're divisible by both <math>15</math> and <math>20</math>, so we have to add <math>33</math> back to the tally (there are <math>33</math> multiples of <math>60</math> that does not exceed <math>2001</math>). Lastly, we have to subtract multiples of both <math>3</math> AND <math>4</math> since we only want multiples of either <math>3</math> or <math>4</math>. This is tantamount to subtracting the number of multiples of <math>12</math>. And there are <math>166</math> such numbers. Let's now collect our numbers and compute the total: <math>667</math> + <math>500</math> - <math>133</math> - <math>100</math> + <math>33</math> - <math>166</math> = <math>\boxed{\textbf{(B)}\ 801}</math>.
 +
 
 +
~ PlainOldNumberTheory
 +
 
 +
 
 +
=== Solution 6===
 +
Similar to @above:
 +
Let the function <math>M_{2001}(n)</math> return how many multiples of <math>n</math> are there not exceeding <math>2001</math>. Then we have that the desired number is:
 +
<cmath>M_{2001}(3)+M_{2001}(4)-M_{2001}(3\cdot 4)-M_{2001}(3 \cdot 5) - M_{2001}(4 \cdot 5)+M_{2001}(3 \cdot 4 \cdot 5)</cmath>
 +
 
 +
Evaluating each of these we get:
 +
<cmath>667+500-166-133-100+33 = 1100-299 = 801.</cmath>
 +
 
 +
Thus, the answer is <math>\boxed{\textbf{(B)}\ 801}.</math>
 +
 
 +
-ConfidentKoala4
 +
 
 +
==Video Solutions==
 +
https://youtu.be/EXWK7U8uXyk
  
−
The second case is more or less the same, except we are applying <math>3</math> and <math>4</math> to <math>5</math>. We must find the cases where the first case over counts multiples of five. Utilizing the floor function again on the fractions <math>\lfloor \frac{2001}{3*5} \rfloor</math>, <math>\lfloor \frac{2001}{4*5} \rfloor</math>, and <math>\lfloor \frac{2001}{3*4*5} \rfloor</math> yields the numbers <math>133</math>, <math>100</math>, and <math>33</math>. The first two numbers counted all the numbers that were multiples of either four with five or three with five less than <math>2001</math>. The third counted the overlapping cases, which we must subtract from the sum of the first two. We do this to reach <math>200</math>. Subtracting this number from the original <math>1001</math> numbers procures <math>\boxed{\textbf{(B)}\ 810}</math>.
+
https://www.youtube.com/watch?v=XHmKu-ZoRxI&feature=youtu.be
  
 
== See Also ==
 
== See Also ==

Latest revision as of 14:20, 30 May 2022

The following problem is from both the 2001 AMC 12 #12 and 2001 AMC 10 #25, so both problems redirect to this page.

Problem

How many positive integers not exceeding $2001$ are multiples of $3$ or $4$ but not $5$?

$\textbf{(A) }768 \qquad \textbf{(B) }801 \qquad \textbf{(C) }934 \qquad \textbf{(D) }1067 \qquad \textbf{(E) }1167$

Solutions

Solution 1

Out of the numbers $1$ to $12$ four are divisible by $3$ and three by $4$, counting $12$ twice. Hence $6$ out of these $12$ numbers are multiples of $3$ or $4$.

The same is obviously true for the numbers $12k+1$ to $12k+12$ for any positive integer $k$.

Hence out of the numbers $1$ to $60=5\cdot 12$ there are $5\cdot 6=30$ numbers that are divisible by $3$ or $4$. Out of these $30$, the numbers $15$, $20$, $30$, $40$, $45$ and $60$ are divisible by $5$. Therefore in the set $\{1,\dots,60\}$ there are precisely $30-6=24$ numbers that satisfy all criteria from the problem statement.

Again, the same is obviously true for the set $\{60k+1,\dots,60k+60\}$ for any positive integer $k$.

We have $1980/60 = 33$, hence there are $24\cdot 33 = 792$ good numbers among the numbers $1$ to $1980$. At this point we already know that the only answer that is still possible is $\boxed{\textbf{(B)}}$, as we only have $20$ numbers left.

By examining the remaining $20$ by hand we can easily find out that exactly $9$ of them match all the criteria, giving us $792+9=\boxed{\textbf{(B) }801}$ good numbers. This is correct.

Solution 2

We can solve this problem by finding the cases where the number is divisible by $3$ or $4$, then subtract from the cases where none of those cases divide $5$. To solve the ways the numbers divide $3$ or $4$ we find the cases where a number is divisible by $3$ and $4$ as separate cases. We apply the floor function to every case to get $\left\lfloor \frac{2001}{3} \right\rfloor$, $\left\lfloor \frac{2001}{4} \right\rfloor$, and $\left\lfloor \frac{2001}{12} \right\rfloor$. The first two floor functions were for calculating the number of individual cases for $3$ and $4$. The third case was to find any overlapping numbers. The numbers were $667$, $500$, and $166$, respectively. We add the first two terms and subtract the third to get $1001$. The first case is finished.

The second case is more or less the same, except we are applying $3$ and $4$ to $5$. We must find the cases where the first case over counts multiples of five. Utilizing the floor function again on the fractions $\left\lfloor \frac{2001}{3\cdot5} \right\rfloor$, $\left\lfloor \frac{2001}{4\cdot5} \right\rfloor$, and $\left\lfloor \frac{2001}{3\cdot4\cdot5} \right\rfloor$ yields the numbers $133$, $100$, and $33$. The first two numbers counted all the numbers that were multiples of either four with five or three with five less than $2001$. The third counted the overlapping cases, which we must subtract from the sum of the first two. We do this to reach $200$. Subtracting this number from the original $1001$ numbers procures $\boxed{\textbf{(B)}\ 801}$.

Solution 3

First find the number of such integers between 1 and 2000 (inclusive) and then add one to this result because 2001 is a multiple of $3$.

There are $\frac45\cdot2000=1600$ numbers that are not multiples of $5$. $\frac23\cdot\frac34\cdot1600=800$ are not multiples of $3$ or $4$, so $800$ numbers are. $800+1=\boxed{\textbf{(B)}\ 801}$

Solution 4

Take a good-sized sample of consecutive integers; for example, the first $25$ positive integers. Determine that the numbers $3, 4, 6, 8, 9, 12, 16, 18, 21,$ and $24$ exhibit the properties given in the question. $25$ is a divisor of $2000$, so there are $\frac{10}{25}\cdot2000=800$ numbers satisfying the given conditions between $1$ and $2000$. Since $2001$ is a multiple of $3$, add $1$ to $800$ to get $800+1=\boxed{\textbf{(B)}\ 801}$.

~ mathmagical

Solution 5

By PIE, there are $1001$ numbers that are multiples of $3$ or $4$ and less than or equal to $2001$. $80\%$ of them will not be divisible by $5$, and by far the closest number to $80\%$ of $1001$ is $\boxed{\textbf{(B)}\ 801}$.

~ Fasolinka

Solution 5

Similar to some of the above solutions. We can divide $2001$ by $3$ and $4$ to find the number of integers divisible by $3$ and $4$. Hence, we find that there are $667$ numbers less than $2001$ that are divisible by $3$, and $500$ numbers that are divisible by $4$. However, we will need to subtract the number of multiples of $15$ from 667 and that of $20$ from $500$, since they're also divisible by 5 which we don't want. There are $133$ + $100$ = $233$ such numbers. Note that during this process, we've subtracted the multiples of $60$ twice because they're divisible by both $15$ and $20$, so we have to add $33$ back to the tally (there are $33$ multiples of $60$ that does not exceed $2001$). Lastly, we have to subtract multiples of both $3$ AND $4$ since we only want multiples of either $3$ or $4$. This is tantamount to subtracting the number of multiples of $12$. And there are $166$ such numbers. Let's now collect our numbers and compute the total: $667$ + $500$ - $133$ - $100$ + $33$ - $166$ = $\boxed{\textbf{(B)}\ 801}$.

~ PlainOldNumberTheory


Solution 6

Similar to @above: Let the function $M_{2001}(n)$ return how many multiples of $n$ are there not exceeding $2001$. Then we have that the desired number is: \[M_{2001}(3)+M_{2001}(4)-M_{2001}(3\cdot 4)-M_{2001}(3 \cdot 5) - M_{2001}(4 \cdot 5)+M_{2001}(3 \cdot 4 \cdot 5)\]

Evaluating each of these we get: \[667+500-166-133-100+33 = 1100-299 = 801.\]

Thus, the answer is $\boxed{\textbf{(B)}\ 801}.$

-ConfidentKoala4

Video Solutions

https://youtu.be/EXWK7U8uXyk

https://www.youtube.com/watch?v=XHmKu-ZoRxI&feature=youtu.be

See Also

2001 AMC 12 (Problems • Answer Key • Resources)
Preceded by
Problem 11 		Followed by
Problem 13
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
2001 AMC 10 (Problems • Answer Key • Resources)
Preceded by
Problem 25 		Followed by
Last Question
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=2001_AMC_12_Problems/Problem_12&oldid=174142"