Difference between revisions of "2017 AIME I Problems/Problem 12"
(→Solution 2(PIE) (Should be explained in more detail)) |
m (→Solution 2(PIE) (Should be explained in more detail)) |
||
Line 15: | Line 15: | ||
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>2^9</math> = <math>512</math> subsets(<math>1</math> isn't needed) we have the following: | Since there are <math>2^9</math> = <math>512</math> subsets(<math>1</math> isn't needed) we have the following: | ||
− | The total number of sets with at least one of the groups (with repeats) | + | <math>...</math> The total number of sets with at least one of the groups (with repeats) |
=<math>2^7 + 2^7 + 2^6 + 2^6</math> | =<math>2^7 + 2^7 + 2^6 + 2^6</math> | ||
= <math>384</math> | = <math>384</math> | ||
− | The total number of sets with at least two of the groups (with repeats) | + | <math>...</math> The total number of sets with at least two of the groups (with repeats) |
= 1st & 2nd pair <math>+</math> 1st & 3rd pair <math>+</math> 1st & 4th pair <math>+</math> 2nd & 3rd pair <math>+</math> 2nd & 4th pair <math>+</math> 3rd & 4th pair | = 1st & 2nd pair <math>+</math> 1st & 3rd pair <math>+</math> 1st & 4th pair <math>+</math> 2nd & 3rd pair <math>+</math> 2nd & 4th pair <math>+</math> 3rd & 4th pair | ||
= <math>2^5 + 2^5 + 2^5 + 2^5 + 2^4 + 2^4</math> | = <math>2^5 + 2^5 + 2^5 + 2^5 + 2^4 + 2^4</math> | ||
= <math>160</math> | = <math>160</math> | ||
− | The total number of sets with at least three of the groups (with repeats) | + | <math>...</math> The total number of sets with at least three of the groups (with repeats) |
= 1st, 2nd, & 3rd groups <math>+</math> 1st, 2nd & 4th groups <math>+</math> 1st, 3rd, & 4th groups <math>+</math> 2nd, 3rd, & 4th groups | = 1st, 2nd, & 3rd groups <math>+</math> 1st, 2nd & 4th groups <math>+</math> 1st, 3rd, & 4th groups <math>+</math> 2nd, 3rd, & 4th groups | ||
= <math>2^4 + 2^3 + 2^3 + 2^3</math> | = <math>2^4 + 2^3 + 2^3 + 2^3</math> | ||
= <math>40</math> | = <math>40</math> | ||
− | The total number of sets with all of the groups. | + | <math>...</math> The total number of sets with all of the groups. |
= <math>2^2</math> | = <math>2^2</math> | ||
= <math>4</math> | = <math>4</math> | ||
<math>(512-(384-160+40-4)) \implies \boxed{252}</math>. | <math>(512-(384-160+40-4)) \implies \boxed{252}</math>. | ||
+ | (Note: If someone can add breaks and maybe help explain why there are powers of 2 that would be good) | ||
==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 21:55, 20 March 2018
Contents
[hide]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) (Should be explained in more detail)
We cannot have the following pairs or triplets: . Since there are = subsets( isn't needed) we have the following: The total number of sets with at least one of the groups (with repeats) = = The total number of sets with at least two of the groups (with repeats) = 1st & 2nd pair 1st & 3rd pair 1st & 4th pair 2nd & 3rd pair 2nd & 4th pair 3rd & 4th pair = = The total number of sets with at least three of the groups (with repeats) = 1st, 2nd, & 3rd groups 1st, 2nd & 4th groups 1st, 3rd, & 4th groups 2nd, 3rd, & 4th groups = = The total number of sets with all of the groups. = = . (Note: If someone can add breaks and maybe help explain why there are powers of 2 that would be good)
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.