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

HMMT February 2014 — Guts Round — Problem 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

解析

[ 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 n a a 1 n and 5 | 2 + . . . +2 . To compute f ( n +1) from f ( n ), we note that given any n -tuple ( a , . . . , a ) such 1 n a a 1 n that 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 n a a n 1 n such that 0 ≤ a , . . . , a ≤ 7 and 5 - 2 + . . . + 2 , so these are in bijection. There are a total of 8 1 n a a n a a 1 n 1 n n -tuples, f ( n ) of which satisfy 5 | 2 + . . . + 2 , so there are 8 − f ( n ) for which 5 - 2 + . . . + 2 . n Therefore, f ( n + 1) = 2(8 − f ( 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.