HMMT 二月 2015 · 冲刺赛 · 第 23 题
HMMT February 2015 — Guts Round — Problem 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 and the sum of its elements is a perfect square. A squarely set Q is called super squarely if it is not a proper subset 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 .)
解析
- [ 14 ] Let S = { 1 , 2 , 4 , 8 , 16 , 32 , 64 , 128 , 256 } . A subset P of S is called squarely if it is nonempty and the sum of its elements is a perfect square. A squarely set Q is called super squarely if it is not a proper subset 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 for n = 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 missing digits (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 as well. 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.