Difference between revisions of "2017 AIME I Problems/Problem 12"
Susanssluk (talk | contribs) m (→Solution 3) |
Thebeast5520 (talk | contribs) |
||
(One intermediate revision by one other user not shown) | |||
Line 1: | Line 1: | ||
==Problem 12== | ==Problem 12== | ||
− | Call a set <math>S</math> product-free if there do not exist <math>a, b, c \in S</math> (not necessarily distinct) such that <math>a b = c</math>. For example, the empty set and the set <math>\{16, 20\}</math> are product-free, whereas the sets <math>\{4, 16\}</math> and <math>\{2, 8, 16\}</math> are not product-free. Find the number of product-free subsets of the set <math>\{1, 2, 3, 4, | + | Call a set <math>S</math> product-free if there do not exist <math>a, b, c \in S</math> (not necessarily distinct) such that <math>a b = c</math>. For example, the empty set and the set <math>\{16, 20\}</math> are product-free, whereas the sets <math>\{4, 16\}</math> and <math>\{2, 8, 16\}</math> are not product-free. Find the number of product-free subsets of the set <math>\{1, 2, 3, 4,..., 7, 8, 9, 10\}</math>. |
==Solution 1 (Casework)== | ==Solution 1 (Casework)== | ||
Line 36: | Line 36: | ||
Hence our answer is <math>128+48+64+12=\boxed{252}</math>. -Stormersyle | Hence our answer is <math>128+48+64+12=\boxed{252}</math>. -Stormersyle | ||
+ | |||
+ | ==Solution 4== | ||
+ | |||
+ | First, ignore 7 as it does not affect any of the other numbers; we can multiply by 2 later (its either in or out). | ||
+ | |||
+ | Next, we do casework based on whether 2, 3, or 5 are in the set (<math>2^3 = 8</math> quick cases). For each of the cases, the numbers will be of two types --- | ||
+ | |||
+ | 1. They cannot be in the set because they form a product | ||
+ | |||
+ | 2. Whether we add the number to the set or not, it does not affect the rest of the numbers. These numbers simply add a factor of 2 to the case. | ||
+ | |||
+ | For example, in the case where all three are present, we can see that <math>4, 6, 9, 10</math> are of type 1. However, <math>8</math> is of type 2. Therefore this case contributes 2. | ||
+ | |||
+ | Summing over the 8 cases we get <math>2 + 4 + 8 + 16 + 16 + 16 + 32 + 32 = 126.</math> Multiplying by <math>2</math> because of the <math>7</math> gives <math>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 19:41, 15 August 2021
Contents
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
Solution 4
First, ignore 7 as it does not affect any of the other numbers; we can multiply by 2 later (its either in or out).
Next, we do casework based on whether 2, 3, or 5 are in the set ( quick cases). For each of the cases, the numbers will be of two types ---
1. They cannot be in the set because they form a product
2. Whether we add the number to the set or not, it does not affect the rest of the numbers. These numbers simply add a factor of 2 to the case.
For example, in the case where all three are present, we can see that are of type 1. However,
is of type 2. Therefore this case contributes 2.
Summing over the 8 cases we get Multiplying by
because of the
gives
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.