British Maths Olympiad 1997 Round 2 Problem 3

My solution to an Olympiad problem.

By Vamshi Jandhyala in mathematics

September 26, 2019

Find the number of polynomials of degree $5$ with distinct coefficients from the set ${1, 2, 3, 4, 5, 6, 7, 8}$ that are divisible by $x^{2}-x + 1$.

Solution

Solution 1

A fifth degree polynomial is of the form $P(x) = ax^{5}+bx^{4}+cx^{3}+dx^{2}+ex+f$.

It is easy to see that $-\omega$ and $-\omega^{2}$ are the roots of $x^{2}-x + 1$.

Therefore for $x^{2}-x + 1$ to divide $P(x)$, we need

$$ \begin{align} P(-\omega)&=&0 \label{y1997r2p3e1} \\
P(-\omega^{2})&=&0 \label{y1997r2p3e2} \end{align} $$

From $\ref{y1997r2p3e1}$ and $\ref{y1997r2p3e2}$, we get

$$ \begin{align} -a\omega^{2} + b\omega - c +d\omega^{2} - e\omega + f &=& 0 \label{y1997r2p3e3}\\
-a\omega + b\omega^{2}-c+d\omega-e\omega^{2}+f &=& 0 \label{y1997r2p3e4} \end{align} $$

Subtracting $\ref{y1997r2p3e4}$ from $\ref{y1997r2p3e3}$ we get

$$ \begin{align} a+b=d+e \end{align} $$

Adding $\ref{y1997r2p3e4}$ and $\ref{y1997r2p3e3}$ we get

$$ \begin{align} b+c=e+f \end{align} $$

Solution 2

sum([1 for a,b,c,d,e,f in permutations(range(1,9),6)
if ((a+b==d+e) and (b+c==e+f))])

Solution 3 (Brute force computational solution)

sum([1 for p in permutations(range(1,9),6)
    if(rem(sum(c*x**i for i,c in enumerate(p)), x**2-x+1, domain=QQ)== 0)])