HMMT 二月 2019 · 冲刺赛 · 第 22 题
HMMT February 2019 — Guts Round — Problem 22
题目详情
- [ 12 ] Determine the number of subsets S of { 1 , 2 , . . . , 1000 } that satisfy the following conditions: • S has 19 elements, and • the sum of the elements in any non-empty subset of S is not divisible by 20.
解析
- [ 12 ] Determine the number of subsets S of { 1 , 2 , . . . , 1000 } that satisfy the following conditions: • S has 19 elements, and • the sum of the elements in any non-empty subset of S is not divisible by 20. Proposed by: Alec Sun ( ) 50 Answer: 8 · 19 First we prove that each subset must consist of elements that have the same residue mod 20. Let a subset consist of elements a , . . . , a , and consider two lists of partial sums 1 19 a , a + a , a + a + a , . . . , a + a + · · · + a 1 1 2 1 2 3 1 2 19 a , a + a , a + a + a , . . . , a + a + · · · + a . 2 1 2 1 2 3 1 2 19 The residues mod 20 of the partial sums in each list must be pairwise distinct, otherwise subtracting the sum with less terms from the sum with more terms yields a subset whose sum of elements is 0 (mod 20) . Since the residues must also be nonzero, each list forms a complete nonzero residue class mod 20. Since the latter 18 sums in the two lists are identical, a ≡ a (mod 20) . By symmetric 1 2 arguments, a ≡ a (mod 20) for any i, j. i j Furthermore this residue 1 ≤ r ≤ 20 must be relatively prime to 20, because if d = gcd( r, 20) > 1 then any 20 /d elements of the subset will sum to a multiple of 20. Hence there are ϕ (20) = 8 possible ( ) 50 residues. Since there are 50 elements in each residue class, the answer is . We can see that any 19 such subset whose elements are a relatively prime residue r (mod 20) works because the sum of any 1 ≤ k ≤ 19 elements will be kr 6 = 0 (mod 20) .