Problem:
Let be a positive integer greater than one and . A subset of is called funny if, of any two distinct elements of whose sum is a power of two, it contains exactly one. How many funny subsets does have?
Problem:
Let be a positive integer greater than one and . A subset of is called funny if, of any two distinct elements of whose sum is a power of two, it contains exactly one. How many funny subsets does have?
Solution:
The number is . We argue by complete induction on and set .
Base case, . This case is clear: all four subsets of are funny.
Inductive step, . So suppose it is already known that has exactly funny subsets. For each funny set of construct the sets
and
Evidently , and are pairwise disjoint. The sets and are funny: to see this, let be distinct elements of whose sum is a power of two; without loss of generality let .
In the case , that is , exactly one of the two is contained in resp. , since is funny.
In the case we have , hence ; since , we have . By the choice of , either lies in or lies in .
The case cannot occur, since then .
Conversely, if is a funny subset of , then evidently is a funny subset of . The element of with is contained in if and only if is not contained in , since is a power of two. Thus, knowing , the funniness of determines, for all elements of with , whether they are contained in ; the only remaining freedom is whether is an element. Hence equals either or , and to each funny subset of exactly two funny subsets of can be assigned. This completes the proof.