Maths Olympiad Prep

Library / /158 of 520

Combinatorics Difficulty 2.5 Junior Find the answer

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

Pick one

Solution

Since an element of a subset is either in or out, the total number of subsets of the 88-element set is 28=2562^8 = 256. However, since we are only concerned about the subsets with at least 11 prime in it, we can use complementary counting to count the subsets without a prime and subtract that from the total. Because there are 44 non-primes, there are 2824=(D) 2402^8 -2^4 = \boxed{\textbf{(D) } 240} subsets with at least 11 prime.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.