Difference between revisions of "2017 AIME I Problems/Problem 12"
(→Solution 2(PIE)) |
|||
| Line 13: | Line 13: | ||
==Solution 2(PIE)== | ==Solution 2(PIE)== | ||
| − | We cannot have the following pairs or triplets: <math>\{2, 4\}, \{3, 9}, \{2, 3, 6\}, \{2, 5, 10\}</math>. | + | We cannot have the following pairs or triplets: <math>\{2, 4\}, \{3, 9\}, \{2, 3, 6\}, \{2, 5, 10\}</math>. |
Since there are <math>512</math> subsets(<math>1</math> isn't needed) we have the following: | Since there are <math>512</math> subsets(<math>1</math> isn't needed) we have the following: | ||
<math>(512-(384-160+40-4)) \implies \boxed{252}</math>. | <math>(512-(384-160+40-4)) \implies \boxed{252}</math>. | ||
| + | |||
==See Also== | ==See Also== | ||
{{AIME box|year=2017|n=I|num-b=11|num-a=13}} | {{AIME box|year=2017|n=I|num-b=11|num-a=13}} | ||
{{MAA Notice}} | {{MAA Notice}} | ||
Revision as of 20:24, 27 June 2017
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 
.
Solution 1(Casework)
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 cannot have the following pairs or triplets: 
.
Since there are 
subsets( isn't needed) we have the following:
.
See Also
| 2017 AIME I (Problems • Answer Key • Resources) | ||
| Preceded by Problem 11 |
Followed by Problem 13 | |
| 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. 
