Difference between revisions of "2017 AIME I Problems/Problem 12"
(Created page with "==Solution== 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=...") |
m |
||
Line 1: | Line 1: | ||
+ | ==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, 5, 6, 7, 8, 9, 10\}</math>. | ||
+ | |||
==Solution== | ==Solution== | ||
Line 8: | Line 11: | ||
So our answer is <math>60+64+128=\boxed{252}</math>. | So our answer is <math>60+64+128=\boxed{252}</math>. | ||
+ | |||
+ | ==See Also== | ||
+ | {{AIME box|year=2017|n=I|num-b=11|num-a=13}} | ||
+ | {{MAA Notice}} |
Revision as of 20:27, 8 March 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
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 S be a product-free set. If the lowest element of S is , we consider the set {3, 6, 9}. We see that of these subsets can be a subset of S ({3}, {6}, {9}, {6, 9}, and the empty set). Now consider the set {5, 10}. We see that of these subsets can be a subset of S ({5}, {10}, and the empty set). Note that cannot be an element of S, because is. Now consider the set {7, 8}. All four of these subsets can be a subset of S. So if the smallest element of S is , there are possible such sets.
If the smallest element of S is , the only restriction we have is that is not in S. This leaves us such sets.
If the smallest element of S is not or , then S can be any subset of {4, 5, 6, 7, 8, 9, 10}, including the empty set. This gives us such subsets.
So our answer 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.