2017 AIME I Problems/Problem 12
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 1. 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
.
Solution 3
Let be a product-free subset, and note that 1 is not in
. We consider four cases: 1.) both 2 and 3 are not in
. Then there are
possible subsets for this case. 2.) 2 is in
, but 3 is not. Then 4 in not in
, so there are
subsets; however, there is a
chance that 5 and 10 are both in
, so there are
subsets for this case. 3.) 2 is not in
, but 3 is. Then, 9 is not in
, so there are
subsets for this case. 4.) 2 and 3 are both in
. Then, 4, 6, and 9 are not in
, so there are
total subsets; however, there is a
chance that 5 and 10 are both in
, so there are
subsets for this case.
Hence our answer is
. -Stormersyle
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.