How many subsets of contain at least one prime number?
- A)
- B)
- C)
- D)
- E)
Answer
D
Key insight
Count all subsets, then take away the ones with no prime at all, which are the subsets made only from 4, 6, 8, 9.
Solution
"At least one prime" covers many different cases. The opposite, "no primes at all", is just one case, so count that and subtract.
1. All subsets. Each of the numbers is either in the subset or not, so there are subsets.
2. Sort the numbers. The primes are . The numbers that are not prime are .
3. Subsets with no prime. These use only . Each of these four is in or out, so there are of them. (This includes the empty set, which has no prime in it.)
4. Subtract. Every other subset has at least one prime:
The answer is .
Why this works
The words "at least one" are a signal to count the opposite. The subsets with none of the special items are easy to count, and taking them away from the total leaves exactly the ones you want.
The trap
Forgetting that the empty set is one of the 16 subsets with no prime, or counting the primes wrong (there are four: 2, 3, 5, 7).
Concise solution
The set has elements, so it has subsets in total.
The primes in the set are ; the non-primes are . A subset contains no prime exactly when it is a subset of , and there are of those (including the empty set).
Every other subset contains at least one prime:
The answer is .
Review in the AoPS books
- Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
- Introduction to Number Theory, Chapter 2: Primes and Composites
- Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.3)
- Introduction to Number Theory, Chapter 4: Prime Factorization (§4.2, §4.4)
Techniques
Count the complement and subtract from the total