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
( )
Answer: 8 ·50
First we prove that each subset must consist of elements that have the same residue mod 20. Let a 19
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 subtractingthe 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 classmod 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
( )
residues. Since there are 50 elements in each residue class, the answer is . We can see that any 50
such subset whose elements are a relatively prime residue r (mod 20) works because the sum of any 19
1 ≤ k ≤ 19 elements will be kr 6 = 0 (mod 20) .