2017 AIME I Problems/Problem 12
Call a set product-free if there do not exist (not necessarily distinct) such that . For example, the empty set and the set are product-free, whereas the sets and are not product-free. Find the number of product-free subsets of the set .
We shall solve this problem by doing casework on the lowest element of the subset. Note that the number cannot be in the subset because . Let be a product-free set. If the lowest element of is , we consider the set . We see that 5 of these subsets can be a subset of (, , , , and the empty set). Now consider the set . We see that 3 of these subsets can be a subset of (, , and the empty set). Note that cannot be an element of , because is. Now consider the set . All four of these subsets can be a subset of . So if the smallest element of is , there are possible such sets.
If the smallest element of is , the only restriction we have is that is not in . This leaves us such sets.
If the smallest element of is not or , then can be any subset of , including the empty set. This gives us such subsets.
So our answer is .
Solution 2 (PIE)
We will consider the subsets that do not contain . A subset is product-free if and only if it does not contain one of the groups or . There are subsets that contain 2 and 4 since each of the seven elements other than 2 and 4 can either be in the subset or not. Similarly, there are subsets that contain 3 and 9, subsets that contain 2, 3, and 6, and subsets that contain 2, 5, and 10. The number of sets that contain one of the groups is: For sets that contain two of the groups, we have: For sets that contain three of the groups, we have: For sets that contain all of the groups, we have: By the principle of inclusion and exclusion, the number of product-free subsets is .
|2017 AIME I (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|