2017 AIME II Problems/Problem 1
Contents
[hide]Problem
Find the number of subsets of that are subsets of neither nor .
Solution 1
The number of subsets of a set with elements is . The total number of subsets of is equal to . The number of sets that are subsets of at least one of or can be found using complimentary counting. There are subsets of and subsets of . It is easy to make the mistake of assuming there are sets that are subsets of at least one of or , but the subsets of are overcounted. There are sets that are subsets of at least one of or , so there are subsets of that are subsets of neither nor . .
Solution 2
Upon inspection, a viable set must contain at least one element from both of the sets and . Since 4 and 5 are included in both of these sets, then they basically don't matter, i.e. if set A is a subset of both of those two then adding a 4 or a 5 won't change that fact. Thus, we can count the number of ways to choose at least one number from 1 to 3 and at least one number from 6 to 8, and then multiply that by the number of ways to add in 4 and 5. The number of subsets of a 3 element set is , but we want to exclude the empty set, giving us 7 ways to choose from or . We can take each of these sets and add in a 4 and/or a 5, which can be done in 4 different ways (by adding both, none, one, or the other one). Thus, the answer is .
Solution 3 (Gets straight to the point)
The set of all subsets of that are disjoint with respect to and are not disjoint with respect to the complements of sets (and therefore not a subset of) and will be named , which has members. The union of each member in and the subsets of will be the members of set , which has members.
Solution by User:a1b2
See Also
2017 AIME II (Problems • Answer Key • Resources) | ||
Preceded by First Problem |
Followed by Problem 2 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.