Construction of polynomials

The polynomial P(x) has the property that P(1), P(2), P(3), P(4), and P(5) are equal to 1, 2, 3, 4, 5 in some order. How many possibilities are there for the polynomial P, given that the degree of P is strictly less than 4?

(Duke Math Meet 2013 Tiebreaker round)

Discussion:

Let \[P(x) = a x^3 + b x^2 + c x + d \]

Suppose P(1), P(2), P(3), P(4) are p,q,r,s respectively. Then in matrix notation we may write:

\[\begin{bmatrix} 1 & 1 & 1 & 1 \\ 8 & 4 & 2 & 1 \\ 27 & 9 & 3 & 1 \\ 64 & 16 & 4 & 1 \end {bmatrix} \cdot \begin{bmatrix} a \\ b\\ c\\ d \end{bmatrix} = \begin{bmatrix} p \\ q \\ r \\ s \end{bmatrix} \]

Here p, q, r, s is a permutation of a selection from 1, 2, 3, 4, 5.

This implies:

\[  \begin{bmatrix} a \\ b\\ c\\ d \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 8 & 4 & 2 & 1 \\ 27 & 9 & 3 & 1 \\ 64 & 16 & 4 & 1 \end{bmatrix} ^{-1} \begin{bmatrix} p \\ q \\ r \\ s \end{bmatrix} \]

Note that \[P(5) = 125a + 25b + 5c + d \] or \[P(5) =\begin{bmatrix} 125 & 25 & 5 & 1 \end{bmatrix} \cdot  \begin{bmatrix} a \\ b\\ c\\ d \end{bmatrix} =\begin{bmatrix} 125 & 25 & 5 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 1 & 1 & 1 \\ 8 & 4 & 2 & 1 \\ 27 & 9 & 3 & 1 \\ 64 & 16 & 4 & 1 \end{bmatrix} ^{-1} \begin{bmatrix} p \\ q \\ r \\ s \end{bmatrix} \]

This implies \[P(5) = \begin{bmatrix} -1 & 4 & -6 & 4 \end{bmatrix} \cdot \begin{bmatrix} p \\ q \\ r \\ s \end{bmatrix} \]

Next we work with cases:

P(5) = 2 or 4 (even) implies p is even (hence 4 or 2 respectively). Since otherwise LHS will odd.

Hence \[-p+ 4q – 6r + 4s = 2 \]. or \[4 \] implies \[4(q + s) = 6r + 6 \].

Therefore \[q + s\] is divisible by 3. This is possible only when q+s = 1+ 5 or 5 +1 and r = 3.

Hence P(5) =2 implies (p,q,r,s) = (4, 1, 3, 5) or (4, 5, 3, 1); P(5) = 4 implies (p,q,r,s) = (2, 1, 3, 5) or (2, 5, 3, 1);

P(5) = 1, 3 or 5 implies p is odd (to maintain parity)

Then \[4q – 6r + 4s \] = 4 (1+3 or 3+1) , 6 (1+5 or 5+1), 8 (3+5 or 5+3)

For each of these sub cases there are 4 ‘solutions’ of (p,q,r,s). (found by similar computations).

Example: if \[P(5) + p = 6 \] then \[4(q+s) = 6(r+1) \]. Clearly q+s is divisible by 3. But that is possible iff q+s = 2+4. This implies r =3.

Hence number of valid polynomials are 16