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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s