Difference between revisions of "2018 AMC 12B Problems/Problem 5"
m (→Solution 1) |
Hh99754539 (talk | contribs) (→Solution 3) |
||
(7 intermediate revisions by 5 users not shown) | |||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
− | How many subsets of | + | How many subsets of <math>\{2,3,4,5,6,7,8,9\}</math> contain at least one prime number? |
− | <math> | + | <math> |
+ | \textbf{(A) } 128 \qquad | ||
+ | \textbf{(B) } 192 \qquad | ||
+ | \textbf{(C) } 224 \qquad | ||
+ | \textbf{(D) } 240 \qquad | ||
+ | \textbf{(E) } 256 | ||
+ | </math> | ||
==Solution 1 == | ==Solution 1 == | ||
− | Since an element of a subset is either in or out, the total number of subsets of the 8 element set is <math>2^8 = 256</math>. However, since we are only concerned about the subsets with at least 1 prime in it, we can use complementary counting to count the subsets without a prime and subtract that from the total. Because there are 4 non-primes, there are <math>2^8 -2^4 = 240</math> subsets with at least | + | Since an element of a subset is either in or out, the total number of subsets of the <math>8</math>-element set is <math>2^8 = 256</math>. However, since we are only concerned about the subsets with at least <math>1</math> prime in it, we can use complementary counting to count the subsets without a prime and subtract that from the total. Because there are <math>4</math> non-primes, there are <math>2^8 -2^4 = \boxed{\textbf{(D) } 240}</math> subsets with at least <math>1</math> prime. |
==Solution 2== | ==Solution 2== | ||
− | We can construct our subset by choosing which primes are included and which composites are included. There are <math>2^4-1</math> ways to select the primes (total subsets minus the empty set) and <math>2^4</math> ways to select the composites. Thus, there are <math>15 | + | We can construct our subset by choosing which primes are included and which composites are included. There are <math>2^4-1</math> ways to select the primes (total subsets minus the empty set) and <math>2^4</math> ways to select the composites. Thus, there are <math>15\cdot16=\boxed{\textbf{(D) } 240}</math> ways to choose a subset of the eight numbers. |
+ | |||
+ | ==Solution 3== | ||
+ | We complement count. We know that we have <math>2^8</math> subsets in all, including the empty subset. We subtract 1 from the total, so we have <math>2^8-1</math>. We also subtract <math>\dbinom{4}{1},\dbinom{4}{2},\dbinom{4}{3}</math>, and <math>\dbinom{4}{4}</math>, because those are the subsets that do not include a prime number. We have four subsets that do not have a prime number and include one composite number, six subsets that have two composite numbers and no primes, four subsets that include three composite numbers and no prime numbers, and finally one subset with four composite numbers and no prime numbers. We have <math>2^8-1-4-6-4-1 = 256-1-4-6-4-1 = 250-1-4-4-1 = \boxed{\textbf{(D) }240}</math> ways to choose a subset of the eight numbers that include a prime number. | ||
+ | |||
+ | == Video Solution == | ||
+ | https://youtu.be/8WrdYLw9_ns?t=253 | ||
+ | |||
+ | ~ pi_is_3.14 | ||
==See Also== | ==See Also== | ||
{{AMC12 box|year=2018|ab=B|num-a=6|num-b=4}} | {{AMC12 box|year=2018|ab=B|num-a=6|num-b=4}} | ||
{{MAA Notice}} | {{MAA Notice}} | ||
+ | |||
+ | [[Category:Introductory Combinatorics Problems]] |
Latest revision as of 22:37, 6 October 2021
Problem
How many subsets of contain at least one prime number?
Solution 1
Since an element of a subset is either in or out, the total number of subsets of the -element set is . However, since we are only concerned about the subsets with at least prime in it, we can use complementary counting to count the subsets without a prime and subtract that from the total. Because there are non-primes, there are subsets with at least prime.
Solution 2
We can construct our subset by choosing which primes are included and which composites are included. There are ways to select the primes (total subsets minus the empty set) and ways to select the composites. Thus, there are ways to choose a subset of the eight numbers.
Solution 3
We complement count. We know that we have subsets in all, including the empty subset. We subtract 1 from the total, so we have . We also subtract , and , because those are the subsets that do not include a prime number. We have four subsets that do not have a prime number and include one composite number, six subsets that have two composite numbers and no primes, four subsets that include three composite numbers and no prime numbers, and finally one subset with four composite numbers and no prime numbers. We have ways to choose a subset of the eight numbers that include a prime number.
Video Solution
https://youtu.be/8WrdYLw9_ns?t=253
~ pi_is_3.14
See Also
2018 AMC 12B (Problems • Answer Key • Resources) | |
Preceded by Problem 4 |
Followed by Problem 6 |
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.