HMMT-Feb 2010 alg, Problem 8

How many polynomials of degree exactly 5 with real coefficients send the set $\{1,2,3,4,5,6\}$ to a permutation of itself?

Solution: For every permutation $\sigma$ of $\{1,2,3,4,5,6\}$, Lagrange Interpolation 1 gives a polynomial of degree at most 5 with $p(x)=\sigma(x)$ for every $x=1,2,3,4,5,6$. Additionally, this polynomial is unique: assume that there exist two polynomials $p, q$ of degree $\leq 5$ such that they map $\{1,2,3,4,5,6\}$ to the same permutation. Then $p-q$ is a nonzero polynomial of degree $\leq 5$ with 6 distinct roots, a contradiction. Thus an upper bound for the answer is $6 !=720$ polynomials. However, not every polynomial obtained by Lagrange interpolation is of degree 5 (for example, $p(x)=$ $x$ ). We can count the number of invalid polynomials using finite differences ${ }^{2}$ A polynomial has degree less than 5 if and only if the sequence of 5 th finite differences is 0 . The 5 th finite difference of $p(1), p(2), p(3), p(4), p(5), p(6)$ is $p(1)-5 p(2)+10 p(3)-10 p(4)+5 p(5)-p(6)$; thus we want to solve $p(1)-5 p(2)+10 p(3)-10 p(4)+5 p(5)-p(6)=0$ with $\{p(1), p(2), p(3), p(4), p(5), p(6)\}=\{1,2,3,4,5,6\}$. Taking the above equation modulo 5 , we get $p(1)=p(6)(\bmod 5) \Longrightarrow\{p(1), p(6)\}=\{1,6\}$. Note that $1-5 p(2)+10 p(3)-10 p(4)+5 p(5)-6=0$ if and only if $6-5 p(5)+10 p(4)-10 p(3)+5 p(2)-1=0$, so we may assume that $p(1)=1$ and double our result later. Then we have $\{p(2), p(3), p(4), p(5)\}=\{2,3,4,5\}$ and \[ -p(2)+2 p(3)-2 p(4)+p(5)=1 \] The above equation taken modulo 2 implies that $p(2), p(5)$ are of opposite parity, so $p(3), p(4)$ are of opposite parity. We do casework on $\{p(2), p(5)\}$ : (a) $p(2)=2, p(5)=3 ; 2 p(3)-2 p(4)=0$ is a contradiction (b) $p(2)=2, p(5)=5 ; 2 p(3)-2 p(4)=-2 \Longrightarrow p(3)-p(4)=-1 \Longrightarrow p(3)=3, p(4)=4$ (c) $p(2)=3, p(5)=2 ; 2 p(3)-2 p(4)=-2 \Longrightarrow p(3)-p(4)=-1 \Longrightarrow p(3)=4, p(4)=5$ (d) $p(2)=3, p(5)=4 ; 2 p(3)-2 p(4)=0$ is a contradiction (e) $p(2)=4, p(5)=3 ; 2 p(3)-2 p(4)=2 \Longrightarrow p(3)-p(4)=1$ but $\{p(3), p(4)\}=\{2,5\}$, contradiction (f) $p(2)=4, p(5)=5 ; 2 p(3)-2 p(4)=0$ is a contradiction (g) $p(2)=5, p(5)=2 ; 2 p(3)-2 p(4)=4 \Longrightarrow p(3)-p(4)=2$, contradiction (h) $p(2)=5, p(5)=4 ; 2 p(3)-2 p(4)=2 \Longrightarrow p(3)-p(4)=1 \Longrightarrow p(3)=3, p(4)=2$ Hence there are a total of $720-2(3)=714$ polynomials. $\fbox{714}$.

Answer: 714