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"

(→‎Video Solutions)
(→‎Solutions)
 
(16 intermediate revisions by 4 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>
  
Line 31: 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>\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.
 
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*5} \right\rfloor</math>, <math>\left\lfloor \frac{2001}{4*5} \right\rfloor</math>, and <math>\left\lfloor \frac{2001}{3*4*5} \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>.
+
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===
 
===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.
+
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*2000=1600</math> numbers that are not multiples of <math>5</math>.  <math>\frac23*\frac34*1600=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>
+
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===
 
===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 <math>\frac{10}{25}*2000=800</math> numbers satisfying the given conditions between 1 and 2000. Since 2001 is a multiple of 3, add 1 to 800 to get <math>800+1=\boxed{\textbf{(B)}\ 801}</math>.
+
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
 
~ 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==
 
==Video Solutions==

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"