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

英文解析

34. [ 25 ] For how many unordered sets { a, b, c, d } of positive integers, none of which exceed 168, do therew x y zexist integers w, x, y, z such that ( − 1) a + ( − 1) b + ( − 1) c + ( − 1) d = 168? If your answer is A and
    | C − A |
    − 3
    the correct answer is C , then your score on this problem will be ⌊ 25 e ⌋ .C
    Answer: 761474 As an approximation, we assume a, b, c, d are ordered to begin with (so wehave to divide by 24 later) and add to 168 with a unique choice of signs; then, it suffices to counte + f + g + h = 168 with each e, f, g, h in [ − 168 , 168] and then divide by 24 (we drop the conditionthat none of them can be zero because it shouldn’t affect the answer that much).
    One way to do this is generating functions. We want the coefficient of t in the generating function 168 − 168 − 167 167 168 4 169 − 168 4 4
    ( t + t + . . . + t + t ) = ( t − t ) / ( t − 1)
    Clearing the negative powers, it suffices to find the coefficient of t in 840
    337 4 4 337 674 1
    ( t − 1) / ( t − 1) = (1 − 4 t + 6 t − . . . ) .
    ( t − 1)4
    To do this we expand the bottom as a power series in t :
    Guts Round
    ( )
    ∑
    n +3
    n 1 = tn ≥ 04
    ( t − 1) 3
    ( ) ( ) ( )
    840+3 840 − 337+3 840 − 674+3
    It remains to calculate − 4 · + 6 · . This is almost exactly equal to
    3 3 3
    3 3 3 71
    (843 − 4 · 506 + 6 · 169 ) ≈ 1 . 83 × 10 .
    Dividing by 24, we arrive at an estimation 762500. Even if we use a bad approximation (850 − 4 ·316
    6 · 24
    3 3
    500 + 6 · 150 ) we get approximately 933000, which is fairly close to the answer.