Let be an integer and the set of all positive integers that are not larger than .
A non-empty subset of is called sum-free if, for all elements belonging to , does not belong to . We allow in this condition.
Prove that has more than distinct sum-free subsets.
Solution
Any non-empty subset of is obviously a sum-free subset of , and there are of these. Also, every non-empty subset of the set of odd numbers in is also a sum-free subset and there are of these. The number of common subsets in the union of these two collections is . So has at least sum-free subsets. Alternatively, for any , and are sum-free subsets of and they are neither subsets of nor of . Together with the non-empty subsets of or of they provide the required sum-free subsets.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.