AMC 10 · 2018 · #5

Grade 7 number-theory

Archetype Overlap / Complement Counting └ Sub-archetype Complement by Subtracting Forbidden Arrangements

prime-numberscombinations-basicexponents complementary-countingsystematic-enumeration ↑ Prerequisites: prime-numberscombinations-basic

📏 Medium solution 💡 2 insights

Problem

Count how many subsets of the 8-element set {2,3,4,5,6,7,8,9} contain at least one prime number.

Pick an answer.

(A)

$text{ 128}$

(B)

$text{ 192}$

(C)

$text{ 224}$

(D)

$text{ 240}$

(E)

$text{ 256}$

AMC 10 2018 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve

Strategy Change Focus / Count the Complement

Tool #16 (Change Focus / Count the Complement): "at least one prime" is awkward to count head-on because a subset could have one, two, three, or four primes. The opposite event — "no prime at all" — is a single clean case, so we count those and subtract from the total. Tool #2 (Make a Systematic List): first sort the eight numbers into primes and composites so we know exactly how many of each there are. Tool #3 (Eliminate Possibilities): the result must be one of the five choices, which lets us confirm 240 and rule out the rest.

1STEP 1

Sort into primes and composites

Label each of the eight numbers: 2,3,5,7 are prime and 4,6,8,9 are composite, giving 4 primes and 4 composites.

primes={2,3,5,7}, composites={4,6,8,9}

2STEP 2

Flip to the complement

Rather than count subsets with a prime directly, count the opposite: (at least one prime) = (all) - (no prime).

#(at least one prime) = #(all) - #(no prime)

3STEP 3

Count all subsets

Each of the 8 numbers is independently in or out, so multiplying the two choices gives 2⁸ = 256 subsets in all.

2⁸ = 256 subsets total

4STEP 4

Count subsets with no prime

A prime-free subset uses only the 4 composites {4,6,8,9}, each in or out, so there are 2⁴ = 16 of them (empty set included).

2⁴ = 16 subsets with no prime

5STEP 5

Subtract to finish

Subtract the prime-free subsets from all subsets: 256 - 16 = 240, which is choice (D).

256 - 16 = 240 → (D)

Answer

text{ 240}

The answer 240 is just under the total 256, which makes sense: only 16 of all subsets avoid every prime, so the vast majority must contain at least one. The split 4 primes and 4 composites is balanced, and 2⁸ - 2⁴ = 256 - 16 = 240 is exact. Choices (A) 128 and (B) 192 are far too small, (E) 256 would wrongly count every subset including the empty set, and (C) 224 = 256 - 32 would mistakenly use 2⁵ composites — only (D) fits.

💡Key takeaway

To count subsets with "at least one" prime, count all 2⁸ = 256 subsets, subtract the 2⁴ = 16 that use only composites, and you get 240.

Sort into primes and composites
Flip to the complement
Count all subsets
Count subsets with no prime
Subtract to finish

Sort into primes and composites

Flip to the complement

Count all subsets

Count subsets with no prime

Subtract to finish

More like this