Problem:
A subset of is called balanced if for all elements and both in , there exists an element in such that divides . Compute the number of nonempty balanced subsets.
Solution
Solution:
We work mod , so the condition becomes that for any , , we have .
First, we prove that must be an arithmetic sequence. Observe that if is balanced, then so is the shift for all , so we can assume . Let be an element of such that is minimal. Observe that for any , we have . Thus, is in for all . Because , this implies for all . We prove the following claim.
Claim 1. For all positive integers , we have .
Proof. We proceed with induction on the number of 1's in the binary representation of .
Base Case: has one 1 in binary, so is a power of 2. Then as noted above.
Induction Step: Assume the claim holds for all which have 1's in their binary representations. Suppose has 1's in its binary representation. Let be the largest power of 2 which is at most . Then has 1's in its binary representation, so does as well. By the induction hypothesis, . Also, , so
as desired.
It follows that every multiple of is in . The multiples of are precisely the multiples of , so contains every multiple of . Now assume for sake of contradiction that contains some element which is not a multiple of , so we can write such that . Then , so
But then , contradicting the minimality of . Thus is precisely the multiples of .
It can be verified that for any , the set of multiples of is balanced. Indeed, as is odd, for any , , their average is a multiple of and hence also in . Thus, any shift of such a set is also balanced; as seen above, these classify all balanced sets. For each , there are choices for , so the answer is