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

英文解析

21. [ 14 ] Compute the number of ordered quintuples of nonnegative integers ( a , a , a , a , a ) such that
    1 2 3 4 5
    a a a a a
    1 2 3 4 5
    0 ≤ a , a , a , a , a ≤ 7 and 5 divides 2 + 2 + 2 + 2 + 2 .
    1 2 3 4 5
    Answer: 6528 Let f ( n ) denote the number of n -tuples ( a , . . . , a ) such that 0 ≤ a , . . . , a ≤ 7
    1 n 1 na a
    1 nand 5 | 2 + . . . +2 . To compute f ( n +1) from f ( n ), we note that given any n -tuple ( a , . . . , a ) such
    1 na a
    1 nthat 0 ≤ a , . . . , a ≤ 7 and 5 - 2 + . . . + 2 , there are exactly two possible values for a such that
    1 n n +1
    a a n
    1 n +1
    0 ≤ a ≤ 7 and 5 | 2 + . . . +2 , because 2 ≡ 1 , 2 , 4 , 3 , 1 , 2 , 4 , 3 (mod 5) for n = 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7
    n +1
    respectively.
    Also, given any valid ( n + 1)-tuple ( a , . . . , a ), we can remove a to get an n -tuple ( a , . . . , a )
    1 n +1 n +1 1 na a n
    1 nsuch that 0 ≤ a , . . . , a ≤ 7 and 5 - 2 + . . . + 2 , so these are in bijection. There are a total of 8
    1 na a n a a
    1 n 1 nn -tuples, f ( n ) of which satisfy 5 | 2 + . . . + 2 , so there are 8 − f ( n ) for which 5 - 2 + . . . + 2 .
    Therefore, f ( n + 1) = 2(8 − f ( n )).n
    We now have f (1) = 0, f (2) = 2(8 − 0) = 16, f (3) = 2(64 − 16) = 96, f (4) = 2(512 − 96) = 832,
    f (5) = 2(4096 − 832) = 6528.