返回题库

HMMT 二月 2017 · ALGNT 赛 · 第 6 题

HMMT February 2017 — ALGNT Round — Problem 6

专题
Discrete Math / 离散数学
难度
L3
来源
HMMT

题目详情

  1. A polynomial P of degree 2015 satisfies the equation P ( n ) = for n = 1 , 2 , . . . , 2016. Find 2 n b 2017 P (2017) c .
解析
  1. A polynomial P of degree 2015 satisfies the equation P ( n ) = for n = 1 , 2 , . . . , 2016. Find 2 n b 2017 P (2017) c . Proposed by: Alexander Katz Answer: − 9 2 2 Let Q ( x ) = x P ( x ) − 1. Then Q ( n ) = n P ( n ) − 1 = 0 for n = 1 , 2 , . . . , 2016, and Q has degree 2017. Thus we may write 2 Q ( x ) = x P ( x ) − 1 = ( x − 1)( x − 2) . . . ( x − 2016) L ( x ) 1 where L ( x ) is some linear polynomial. Then Q (0) = − 1 = ( − 1)( − 2) . . . ( − 2016) L (0), so L (0) = − . 2016! Now note that ′ 2 ′ Q ( x ) = x P ( x ) + 2 xP ( x ) 2016 ∑ ′ = ( x − 1) . . . ( x − ( i − 1))( x − ( i + 1)) . . . ( x − 2016) L ( x ) + ( x − 1)( x − 2) . . . ( x − 2016) L ( x ) i =1 Thus ( ) 2016! 2016! 2016! ′ ′ Q (0) = 0 = L (0) + + . . . + + 2016! L (0) − 1 − 2 − 2016 ( ) 1 1 1 H ′ 2016 whence L (0) = L (0) + + . . . + = − , where H denotes the n th harmonic number. n 1 2 2016 2016! H x +1 2016 As a result, we have L ( x ) = − . Then 2016! ( ) 2017 H + 1 2016 2 Q (2017) = 2017 P (2017) − 1 = 2016! − 2016! which is − 2017 H − 1. Thus 2016 − H 2016 P (2017) = . 2017 From which we get 2017 P (2017) = − H . It remains to approximate H . We alter the well known 2016 2016 approximation ∫ n 1 H ≈ dx = log x n x 1 to ∫ n 1 1 1 1 H ≈ 1 + + dx = 1 + + log(2016) − log(3) ≈ log(2016) + n 2 x 2 2 3 3 so that it suffices to lower bound log(2016). Note that e ≈ 20, which is close enough for our purposes. 6 7 3 5 0 . 6 7 . 6 Then e ≈ 400 = ⇒ e ≈ 1080, and e ≈ 20 < 2 = ⇒ e << 2 = ⇒ e < 2016, so that log(2016) > 7 . 6. It follows that H ≈ log(2016) + 0 . 5 = 7 . 6 + 0 . 5 > 8 (of course these are loose 2016 estimates, but more than good enough for our purposes). Thus − 9 < 2017 P (2017) < − 8, making our answer − 9 . Alternatively, a well-read contestant might know that H ≈ log n + γ , where γ ≈ . 577 is the Euler- n Mascheroni constant. The above solution essentially approximates γ as 0 . 5 which is good enough for our purposes.