HMMT 二月 2011 · ALGCALC 赛 · 第 14 题

英文解析

14. How many polynomials P with integer coefficients and degree at most 5 satisfy 0 ≤ P ( x ) < 120 for allx ∈ { 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 formn 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 coefficientc , then by matching leading coefficients we must have m = n and a = c . By the induction hypothesis,
    n n − 1 1 0 nf ( 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 havei − 1
    P ( i ) = a i ! + a i + · · · + ai i − 1 0
    i − 1
    so by choosing a we can make P ( i ) any number congruent to a i + · · · + a modulo i !. Thus therei i − 1 0
    are choices for a . Note the choice of a does not affect the value of P (0) , . . . , P ( i − 1). Thus all 120
    i ii !
    polynomials we obtain in this way are valid. The answer is
    ∏5 = 86400000 .120
    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 !