Monic polynomial divisible by 2018

Let $P(x)$ a monic polynomial (polynomial having leading coefficient one) with integer coefficients such that $P(k)$ is divisible by 2018 for all integer $k$. Find the smallest possible degree of $P$

Solution

Note that $P(x) = x(x+1)(x+1) \dots (x+1008)$ is always divisible by 1009, because one of the factors is always divisible by 1009. It's also even. Therefore $P(x)$ is a polynomial that satisfies the problem requirement, having degree 1009. We shall show that this degree is minimal.

We call a polynomial (not necessarily monic) "good" if it has property that $P(k)$ is divisible by 2018 for all integer $k$.

Suppose $P_n(x)$ is a good monic polynomial having degree $n$, then we apply the following procedure: let $P_{n-1}(x) = P_n(x+1) - P_n(x)$. Then $P_{n-1}$ is a polynomial of degree $n-1$ (because the $x^n$ terms cancel out). Because $P_n$ is good, then $P_{n-1}$ is also good. Furthermore, the leading coefficient of $P_{n-1}$ is $n$, because the only source of $x^{n-1}$ terms is from the expansion of $(x+1)^n$. The other $x^{n-1}$ terms cancel out as well.

We continue this process to obtain $P_{n-2}, P_{n-3},$ and so on. At each step, define $P_m(x) = P_{m+1}(x+1) - P_{m+1}(x)$. We claim the following facts:

1. $P_m$ is good

2. The leading coefficient of $P_m$ is $n(n-1)(n-2) \dots (m+1) = \frac{n!}{m!}$

The two facts can be shown simultaneously using induction. It's obviously true for $m=n$, and as we demonstrated, it's also true for $m=n-1$. If it's true for $m+1$ then it's easy to see that it's true for $m$ as well, using the same argument we showed above.

Thus, at some point, we will arrive at $P_0$ having leading coefficient $n!$. That is, $P_0(x) = n!$ for all $x$, and this must be divisible by 2018 because $P_0$ is good. Therefore $n!$ is divisible by 2018.

What we showed was the necessary condition for a monic polynomial to be good. That is, if it has degree $n$ then $n!$ is divisible by 2018. The smallest possible such $n$ is 1009 because 1009 is prime. But we also showed a sufficient condition, that there exists a polynomial with degree 1009 that's both monic and good. Thus the answer is 1009.

Non-attacking rooks

Given an $n \times n$ chess board and $2n+1$ rooks placed on it, prove that we will always be able to choose 3 rooks who can't attack each other.

Solution

Partition the board into $n$ groups in a "broken diagonal" pattern. That is, cell $(i,j)$ belongs to group $i+nj \mod n$. Two cells in the same group can't attack each other (easily shown either by diagonal argument or modular analysis).

Because there are $2n+1$ rooks, then there are 3 rooks that sit on the same group.

Product of cosines

For $n$ natural number, and $a = \frac{2\pi}{2n+1}$ find the value of $$\cos a . \cos 2a . \cos 3a . \dots . \cos na$$

Solution

We first prove the following claim: for any $n$ positive odd number, $$\sin (nx) = \sin x P_n (\cos x)$$ $$\cos (nx) = \cos x Q_n (\cos x)$$ where $P_n(t)$ and $Q_n(t)$ are polynomials in the form of $2^{n-1} t^{n-1} + ...$ (In other words, they have degree $n-1$ and the leading coefficient $2^{n-1}$

Proof by induction, evident for $n=1$ and $n=3$. Inductive step: $$\sin (n+2)x = \sin nx \cos 2x + \cos nx \sin 2x = \sin x P_n (\cos x) (2 \cos^2 x - 1) + \cos x Q_n (\cos x) .2\sin x \cos x$$ $$ = \sin x ( P_n (\cos x) (2 \cos^2 x - 1) + 2\cos^2 x Q_n (\cos x) ) = \sin x P_{n+2} (\cos x)$$ where $P_{n+2}$ has degree $n+2$ and the leading coefficient $2. 2^{n-1} + 2.2^{n-1} = 2^{n+1}$

Likewise: $$\cos (n+2) x = \cos nx \cos 2x - \sin nx \sin 2x = \cos x Q_n(\cos x)(2 \cos^2 x - 1) - \sin x P_n (\cos x) . 2 \sin x \cos x$$ $$ = \cos x ( Q_n(\cos x)(2 \cos^2 x - 1) - 2 P_n (\cos x) (1 - \cos^2 x)) = \cos x Q_{n+2} (\cos x)$$ like before, the polynomial $Q_{n+2}$ has degree $n+2$ and leading coefficient $2^{n+1}$

So now, observe that $x = 0,a,2a, \dots, 2na$ are all solutions of the equation $$\cos (2n+1)x = 1 = \cos x Q_{2n+1}(\cos x)$$ Therefore $t = \cos 0, \cos a, \dots, \cos 2na$ are all roots of the polynomial $$ S(t) = tQ_{2n+1}(t) - 1$$ Because $S(t)$ has degree $2n+1$, then $\cos 0, \dots \cos 2na$ are ALL of the roots, and the product of all those roots is $\frac{1}{2^{2n}}$ (because $S(t)$ has leading coefficient $2^{2n}$

Now, $\cos a = \cos 2n a, \cos 2a = \cos (n-1) a$ and so on. So: $$\cos 0 . \cos a .\dots. \cos 2na = 1 . (\cos a. \dots . \cos na)^2 = \frac{1}{2^{2n}}$$ So: $$\cos a . \dots . \cos na = \frac{1}{2^n}$$