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=...") |
(No difference)
|
Revision as of 16:49, 8 March 2017
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 .