HMMT 二月 2013 · 冲刺赛 · 第 21 题

英文解析

21. [ 14 ] Find the number of positive integers j ≤ 3 such thatm
    ( )
    ∑
    j = ( − 1) · 3 kakk =0
    for some strictly increasing sequence of nonnegative integers { a } . For example, we may write 3 = 31
    0 3 4 kand 55 = 3 − 3 + 3 , but 4 cannot be written in this form.
    2013
    Answer: 2 Clearly m must be even, or the sum would be negative. Furthermore, if a ≤ 2013,
    ( )m
    ∑
    m − 1 k
    2013 a a am k mthe sum cannot exceed 3 since j = 3 + ( − 1) · 3 ≤ 3 . Likewise, if a > 2013, thenmk =0
    2013
    the sum necessarily exceeds 3 , which is not hard to see by applying the Triangle Inequality andsumming a geometric series. Hence, the elements of { a } can be any subset of { 0 , 1 , . . . , 2013 } with anodd number of elements. Since the number of even-sized subsets is equal to the number of odd-sizedk
    2014
    20132
    elements, there are = 2 such subsets.
    Now, it suffices to show that given such an { a } , the value of j can only be obtained in this way. Suppose 2
    for the the sake of contradiction that there exist two such sequences { a } and { b }kk 0 ≤ k ≤ m k 0 ≤ k ≤ ma bwhich produce the same value of j for j positive or negative, where we choose { a } , { b } such thatk ka a ( a − 1) 0 1
    0 1 mamin( m , m ) is as small as possible. Then, we note that since 3 + 3 + . . . + 3 ≤ 3 + 3 +
    a b
    ( )
    ∑
    m ka
    ( a ) ( a − 1) a ( a − 1)
    ma − 1 ma k ma
    . . . + 3 < 2(3 ), we have that ( − 1) · 3 > 3 . Similarly, we get thatk =0
    ( )
    ∑
    m kb
    ( a − 1) a ( m − 1)
    m k bb
    3 ≥ ( − 1) · 3 > 3 ; for the two to be equal, we must have m = m . However,
    a bk =0
    this means that the sequences obtained by removing a and a from { a } { b } have smaller maximumm m k ka bvalue but still produce the same alternating sum, contradicting our original assumption.
    Guts Round