HMMT 二月 2023 · ALGNT 赛 · 第 10 题
HMMT February 2023 — ALGNT Round — Problem 10
题目详情
- Let ζ = e and ω = e . The polynomial 9999 9998 x + a x + · · · + a x + a 9998 1 0 m n has roots ζ + ω for all pairs of integers ( m, n ) with 0 ≤ m < 99 and 0 ≤ n < 101. Compute a + a + · · · + a . 9799 9800 9998
解析
- Let ζ = e and ω = e . The polynomial 9999 9998 x + a x + · · · + a x + a 9998 1 0 m n has roots ζ + ω for all pairs of integers ( m, n ) with 0 ≤ m < 99 and 0 ≤ n < 101. Compute a + a + · · · + a . 9799 9800 9998 Proposed by: Sean Li ( ) 9999 200 Answer: 14849 − 200 99 Solution: Let b := a for sake of brevity, so we wish to compute b + b + · · · + b . Let p be k 9999 − k 1 2 200 k m n the sum of the k -th powers of ζ + ω over all ordered pairs ( m, n ) with 0 ≤ m < 99 and 0 ≤ n < 101. Recall that Newton’s sums tells us that p + b = 0 1 1 p + p b + 2 b = 0 2 1 1 2 p + p b + p b + 3 b = 0 3 2 1 1 2 3 . . . ∑ k and in general kb + p b = 0. The key idea is that p is much simpler to compute than b , k j k − j k k j =1 and we can relate the two with Newton’s sums. The roots of unity filter identity tells us that if P ( s, t ) is a two-variable polynomial, then z ( P ) := ∑ 1 m n P ( ζ , ω ) over all 0 ≤ m < 99 and 0 ≤ n < 101 is exactly the sum of the coefficients of the 9999 99 a 101 b k terms s t . Suppose that P ( s, t ) = ( s + t ) . Then z ( P ) is precisely p / 9999. So one can check k k k that 98 99 a 101 b • if k 6 = 99 , 101 , 198 , 200, then ( s + t ) has no terms of the form s t and so p = 0. k • if k = 99 , 101 , 198, then z ( P ) = 1 and p = 9999. k k ( ) ( ) 200 200 • if k = 200, then z ( P ) = and p = 9999 . k k 99 99 We can now compute b using Newton’s sums identities: k • we have b = 0 for k 6 = 99 , 101 , 198 , 200. k • since p + 99 b = 0, we have b = − 101; 99 99 99 • since p + 101 b = 0, we have b = − 99; 101 101 101 • since p + p b + 198 b = 0, we have 198 99 99 198 1 1 b = ( − p − p b ) = ( − 9999 + 9999 · 101) = 5050 . · 198 198 99 99 198 198 • since p + p b + p b + 200 b = 0, we have 200 101 99 99 101 200 1 b = ( − p − p b − p b ) 200 200 101 99 99 101 200 ( ( ) ) 1 200 = − 9999 + 9999 · 101 + 9999 · 99 200 99 ( ) 9999 200 = 9999 − . 200 99 Hence, we have ( ) 9999 200 b + b + · · · + b = − 101 − 99 + 5050 + 9999 − 1 2 200 200 99 ( ) 9999 200 = 14849 − . 200 99