# 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