Maths Olympiad Prep

Library / /1258 of 1394

Combinatorics Difficulty 5.9 AIME, harder Prove it United States

Problem:
Let S={1,2,4,8,16,32,64,128,256}S=\{1,2,4,8,16,32,64,128,256\}. A subset PP of SS is called squarely if it is nonempty and the sum of its elements is a perfect square. A squarely set QQ is called super squarely if it is not a proper subset of any squarely set. Find the number of super squarely sets.
(A set AA is said to be a proper subset of a set BB if AA is a subset of BB and ABA \neq B.)

Solution

Solution:
Answer: 5 Clearly we may biject squarely sets with binary representations of perfect squares between 1 and 20++28=291=5112^{0}+\cdots+2^{8}=2^{9}-1=511, so there are 22 squarely sets, corresponding to n2n^{2} for n=1,2,,22n=1,2, \ldots, 22. For convenience, we say NN is (super) squarely if and only if the set corresponding to NN 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; (2k)2(2k)^{2} is just k2k^{2} with two additional zeros at the end. 1,9,25,49,811,9,25,49,81 are ineffective, but 121=277=26+25+24+23+20121=2^{7}-7=2^{6}+2^{5}+2^{4}+2^{3}+2^{0} immediately rules out all odd squares up to 929^{2}, as they must be 1(mod8)1\pmod{8}.
Fortunately, 222=411222^{2}=4 \cdot 11^{2} is in our range (i.e. less than 512), ruling out all even squares up to 20220^{2} as well.
This leaves us with 112,132,152,172,192,212,22211^{2}, 13^{2}, 15^{2}, 17^{2}, 19^{2}, 21^{2}, 22^{2}, with binary representations 001111001, 010101001, 011100001,100100001,101101001011100001, 100100001, 101101001 (kills 17217^{2}), 110111001 (kills 13213^{2}), 111100100 (kills nothing by parity). Thus 112,152,192,212,22211^{2}, 15^{2}, 19^{2}, 21^{2}, 22^{2} are the only super squarely numbers, for a total of 5.

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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.