Problem:
Let . A subset of is called squarely if it is nonempty and the sum of its elements is a perfect square. A squarely set is called super squarely if it is not a proper subset of any squarely set. Find the number of super squarely sets.
(A set is said to be a proper subset of a set if is a subset of and .)
Solution
Solution:
Answer: 5 Clearly we may biject squarely sets with binary representations of perfect squares between 1 and , so there are 22 squarely sets, corresponding to for . For convenience, we say is (super) squarely if and only if the set corresponding to is (super) squarely.
The general strategy is to rule out lots of squares at a time, by searching for squares with few missing digits (and ideally most 1's consecutive, for simplicity). We can restrict ourselves (for now) to odds; is just with two additional zeros at the end. are ineffective, but immediately rules out all odd squares up to , as they must be .
Fortunately, is in our range (i.e. less than 512), ruling out all even squares up to as well.
This leaves us with , with binary representations 001111001, 010101001, (kills ), 110111001 (kills ), 111100100 (kills nothing by parity). Thus are the only super squarely numbers, for a total of 5.