返回题库

HMMT 二月 2019 · 冲刺赛 · 第 22 题

HMMT February 2019 — Guts Round — Problem 22

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [ 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.
解析

英文解析

  1. [ 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) .