Difference between revisions of "2017 AIME I Problems/Problem 12"
m (→Solution 2(PIE) (Should be explained in more detail)) |
(→Solution 2(PIE) (Should be explained in more detail)) |
||
Line 12: | Line 12: | ||
So our answer is <math>60+64+128=\boxed{252}</math>. | So our answer is <math>60+64+128=\boxed{252}</math>. | ||
− | ==Solution 2(PIE | + | ==Solution 2 (PIE)== |
− | We | + | We will consider the <math>2^9 = 512</math> subsets that do not contain <math>1</math>. A subset is product-free if and only if it does not contain one of the groups <math>\{2, 4\}, \{3, 9\}, \{2, 3, 6\},</math> or <math>\{2, 5, 10\}</math>. There are <math>2^7</math> 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 <math>2^7</math> subsets that contain 3 and 9, <math>2^6</math> subsets that contain 2, 3, and 6, and <math>2^6</math> subsets that contain 2, 5, and 10. The number of sets that contain one of the groups is: |
− | + | <cmath>2^7 + 2^7 + 2^6 + 2^6 = 384</cmath> | |
− | <math> | + | For sets that contain two of the groups, we have: |
− | + | <cmath>2^5 + 2^5 + 2^5 + 2^5 + 2^4 + 2^4 = 160</cmath> | |
− | = | + | For sets that contain three of the groups, we have: |
− | + | <cmath>2^4 + 2^3 + 2^3 + 2^3 = 40</cmath> | |
− | + | For sets that contain all of the groups, we have: | |
− | + | <cmath>2^2 = 4</cmath> | |
− | = | + | By the principle of inclusion and exclusion, the number of product-free subsets is |
− | + | <cmath>512 - (384 - 160 + 40 - 4) = \boxed{252}</cmath>. | |
− | |||
− | |||
− | = | ||
− | |||
− | |||
− | = | ||
− | < | ||
− | |||
==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 16:08, 27 March 2018
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 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
.
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.