Problem:
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:
Let be a product-free subset of . First note that because . Assume is nonempty and let be the least element of . Note that if , then the least possible product of any two elements of is ; hence any subset of will be product-free. Counting the empty set, there are such subsets.
Next, suppose that . Then , and and can be in (or not). The remaining elements of to consider are the multiples of and . The possible subsets of that contain only multiples of are , and . Similarly, the possible subsets of that contain only multiples of are , and . Thus there are product-free subsets of that contain .
If , then and cannot be in . Any of the values in may or may not be in , providing product-free subsets with as the least element. Therefore the requested number of subsets is .
The problems on this page are the property of the MAA's American Mathematics Competitions