Difference between revisions of "2017 AIME I Problems/Problem 12"
m (bottom box, formatting) |
|||
Line 2: | Line 2: | ||
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, 5, 6, 7, 8, 9, 10\}</math>. | 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, 5, 6, 7, 8, 9, 10\}</math>. | ||
− | ==Solution== | + | ==Solution 1(Casework)== |
We shall solve this problem by doing casework on the lowest element of the subset. Note that the number <math>1</math> cannot be in the subset because <math>1*1=1</math>. Let <math>S</math> be a product-free set. If the lowest element of <math>S</math> is <math>2</math>, we consider the set <math>\{3, 6, 9\}</math>. We see that 5 of these subsets can be a subset of <math>S</math> (<math>\{3\}</math>, <math>\{6\}</math>, <math>\{9\}</math>, <math>\{6, 9\}</math>, and the empty set). Now consider the set <math>\{5, 10\}</math>. We see that 3 of these subsets can be a subset of <math>S</math> (<math>\{5\}</math>, <math>\{10\}</math>, and the empty set). Note that <math>4</math> cannot be an element of <math>S</math>, because <math>2</math> is. Now consider the set <math>\{7, 8\}</math>. All four of these subsets can be a subset of <math>S</math>. So if the smallest element of <math>S</math> is <math>2</math>, there are <math>5*3*4=60</math> possible such sets. | We shall solve this problem by doing casework on the lowest element of the subset. Note that the number <math>1</math> cannot be in the subset because <math>1*1=1</math>. Let <math>S</math> be a product-free set. If the lowest element of <math>S</math> is <math>2</math>, we consider the set <math>\{3, 6, 9\}</math>. We see that 5 of these subsets can be a subset of <math>S</math> (<math>\{3\}</math>, <math>\{6\}</math>, <math>\{9\}</math>, <math>\{6, 9\}</math>, and the empty set). Now consider the set <math>\{5, 10\}</math>. We see that 3 of these subsets can be a subset of <math>S</math> (<math>\{5\}</math>, <math>\{10\}</math>, and the empty set). Note that <math>4</math> cannot be an element of <math>S</math>, because <math>2</math> is. Now consider the set <math>\{7, 8\}</math>. All four of these subsets can be a subset of <math>S</math>. So if the smallest element of <math>S</math> is <math>2</math>, there are <math>5*3*4=60</math> possible such sets. | ||
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)== | ||
+ | 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: | ||
+ | <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 21:23, 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: $\{2, 4\}, \{3, 9}, \{2, 3, 6\}, \{2, 5, 10\}$ (Error compiling LaTeX. Unknown error_msg).
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.