HMMT-Feb 2011 gen, Problem 14

How many polynomials $P$ with integer coefficients and degree at most 5 satisfy $0 \leq P(x)<120$ for all $x \in\{0,1,2,3,4,5\}$ ?

Solution: For each nonnegative integer $i$, let $x^{\underline{i}}=x(x-1) \cdots(x-i+1)$. (Define $x^{\underline{0}}=1$.) Lemma: Each polynomial with integer coefficients $f$ can be uniquely written in the form \[ f(x)=a_{n} x^{\underline{n}}+\ldots+a_{1} x^{\underline{1}}+a_{0} x^{\underline{0}}, a_{n} \neq 0 \] 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_{n}=c$. By the induction hypothesis, $f(x)-c x^{\underline{n}}$ can be uniquely written as $a_{n-1} x^{\underline{n-1}}(x)+\ldots+a_{1} x^{\underline{1}}+a_{0} x^{\underline{0}}$. There are 120 possible choices for $a_{0}$, namely any integer in $[0,120)$. Once $a_{0}, \ldots, a_{i-1}$ have been chosen so $0 \leq P(0), \ldots, P(i-1)<120$, for some $0 \leq i \leq 5$, then we have \[ P(i)=a_{i} i !+a_{i-1} i \frac{i-1}{\underline{i-1}}+\cdots+a_{0} \] so by choosing $a_{i}$ we can make $P(i)$ any number congruent to $a_{i-1} i \underline{i-1}+\cdots+a_{0}$ modulo $i$ !. Thus there are $\frac{120}{i !}$ choices for $a_{i}$. Note the choice of $a_{i}$ does not affect the value of $P(0), \ldots, P(i-1)$. Thus all polynomials we obtain in this way are valid. The answer is \[ \prod_{i=0}^{5} \frac{120}{i !}=86400000 \] Note: Their is also a solution involving finite differences that is basically equivalent to this solution. One proves that for $i=0,1,2,3,4,5$ there are $\frac{5 !}{i !}$ ways to pick the $i$ th finite difference at the point 0 . $\fbox{86400000}$.

Answer: 86400000