HMMT 二月 2015 · 冲刺赛 · 第 23 题

英文解析

23. [ 14 ] Let S = { 1 , 2 , 4 , 8 , 16 , 32 , 64 , 128 , 256 } . A subset P of S is called squarely if it is nonempty andthe sum of its elements is a perfect square. A squarely set Q is called super squarely if it is not a propersubset of any squarely set. Find the number of super squarely sets.
    (A set A is said to be a proper subset of a set B if A is a subset of B and A 6 = B .)
    Answer: 5 Clearly we may biject squarely sets with binary representations of perfect squares
    0 8 9 2
    between 1 and 2 + · · · + 2 = 2 − 1 = 511, so there are 22 squarely sets, corresponding to n forn = 1 , 2 , . . . , 22. For convenience, we say N is (super) squarely if and only if the set corresponding to
    N is (super) squarely.
    The general strategy is to rule out lots of squares at time, by searching for squares with few missingdigits (and ideally most 1’s consecutive, for simplicity). We can restrict ourselves (for now) to odds;
    2 2 7
    (2 k ) is just k with two additional zeros at the end. 1 , 9 , 25 , 49 , 81 are ineffective, but 121 = 2 − 7 =
    6 5 4 3 0 2
    2 + 2 + 2 + 2 + 2 immediately rules out all odd squares up to 9 , as they must be 1 (mod 8).
    2 2 2
    Fortunately, 22 = 4 · 11 is in our range (i.e. less than 512), ruling out all even squares up to 20 aswell.
    2 2 2 2 2 2 2
    This leaves us with 11 , 13 , 15 , 17 , 19 , 21 , 22 , with binary representations 001111001, 010101001,
    2 2
    011100001, 100100001, 101101001 (kills 17 ), 110111001 (kills 13 ), 111100100 (kills nothing by parity).
    2 2 2 2 2
    Thus 11 , 15 , 19 , 21 , 22 are the only super squarely numbers, for a total of 5.