HMMT 二月 2011 · ALGCOMB 赛 · 第 13 题
HMMT February 2011 — ALGCOMB Round — Problem 13
题目详情
- How many polynomials P with integer coefficients and degree at most 5 satisfy 0 ≤ P ( x ) < 120 for all x ∈ { 0 , 1 , 2 , 3 , 4 , 5 } ?
解析
- How many polynomials P with integer coefficients and degree at most 5 satisfy 0 ≤ P ( x ) < 120 for all x ∈ { 0 , 1 , 2 , 3 , 4 , 5 } ? i 0 Answer: 86400000 For each nonnegative integer i , let x = x ( x − 1) · · · ( x − i + 1). (Define x = 1.) Lemma: Each polynomial with integer coefficients f can be uniquely written in the form n 1 0 f ( x ) = a x + . . . + a x + a x , a 6 = 0 . n 1 0 n Proof: Induct on the degree. The base case (degree 0) is clear. If f has degree m with leading coefficient c , then by matching leading coefficients we must have m = n and a = c . By the induction hypothesis, n n n − 1 1 0 f ( x ) − cx can be uniquely written as a x ( x ) + . . . + a x + a x . n − 1 1 0 There are 120 possible choices for a , namely any integer in [0 , 120). Once a , . . . , a have been 0 0 i − 1 chosen so 0 ≤ P (0) , . . . , P ( i − 1) < 120, for some 0 ≤ i ≤ 5, then we have i − 1 P ( i ) = a i ! + a i + · · · + a i i − 1 0 i − 1 so by choosing a we can make P ( i ) any number congruent to a i + · · · + a modulo i !. Thus there i i − 1 0 120 are choices for a . Note the choice of a does not affect the value of P (0) , . . . , P ( i − 1). Thus all i i i ! polynomials we obtain in this way are valid. The answer is 5 ∏ 120 = 86400000 . i ! i =0 Note: Their is also a solution involving finite differences that is basically equivalent to this solution. 5! One proves that for i = 0 , 1 , 2 , 3 , 4 , 5 there are ways to pick the i th finite difference at the point 0. i ! Algebra & Combinatorics Individual Test