HMMT 二月 2013 · 冲刺赛 · 第 34 题
HMMT February 2013 — Guts Round — Problem 34
题目详情
- [ 25 ] For how many unordered sets { a, b, c, d } of positive integers, none of which exceed 168, do there w x y z exist 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 C the correct answer is C , then your score on this problem will be b 25 e c .
解析
- [ 25 ] For how many unordered sets { a, b, c, d } of positive integers, none of which exceed 168, do there w x y z exist 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 C the correct answer is C , then your score on this problem will be ⌊ 25 e ⌋ . Answer: 761474 As an approximation, we assume a, b, c, d are ordered to begin with (so we have to divide by 24 later) and add to 168 with a unique choice of signs; then, it suffices to count e + f + g + h = 168 with each e, f, g, h in [ − 168 , 168] and then divide by 24 (we drop the condition that none of them can be zero because it shouldn’t affect the answer that much). 168 One way to do this is generating functions. We want the coefficient of t in the generating function − 168 − 167 167 168 4 169 − 168 4 4 ( t + t + . . . + t + t ) = ( t − t ) / ( t − 1) 840 Clearing the negative powers, it suffices to find the coefficient of t in 337 4 4 337 674 1 ( t − 1) / ( t − 1) = (1 − 4 t + 6 t − . . . ) . 4 ( t − 1) To do this we expand the bottom as a power series in t : Guts Round ( ) ∑ n +3 1 n = t 4 n ≥ 0 ( 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 1 3 3 3 7 (843 − 4 · 506 + 6 · 169 ) ≈ 1 . 83 × 10 . 6 1 3 Dividing by 24, we arrive at an estimation 762500. Even if we use a bad approximation (850 − 4 · 6 · 24 3 3 500 + 6 · 150 ) we get approximately 933000, which is fairly close to the answer.