2018 AMC 10B Problem 5

P1-10~2 minPrint

Basic Counting Primes Count the complement and subtract from the total

How many subsets of $\{2,3,4,5,6,7,8,9\}$ contain at least one prime number?

Show solution without answering

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 $8$ numbers is either in the subset or not, so there are $2^8 = 256$ subsets.
2. Sort the numbers. The primes are $2, 3, 5, 7$ . The numbers that are not prime are $4, 6, 8, 9$ .
3. Subsets with no prime. These use only $4, 6, 8, 9$ . Each of these four is in or out, so there are $2^4 = 16$ of them. (This includes the empty set, which has no prime in it.)
4. Subtract. Every other subset has at least one prime:
$256 - 16 = 240.$

The answer is $\boxed{\textbf{(D)}\ 240}$ .

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.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

The set has $8$ elements, so it has $2^8 = 256$ subsets in total.

The primes in the set are $2, 3, 5, 7$ ; the non-primes are $4, 6, 8, 9$ . A subset contains no prime exactly when it is a subset of $\{4, 6, 8, 9\}$ , and there are $2^4 = 16$ of those (including the empty set).

Every other subset contains at least one prime:
$256 - 16 = 240.$

The answer is $\boxed{\textbf{(D)}\ 240}$ .

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)