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.

Flea on a regular polygon

We are given a regular $N$-gon. A flea originally sits on one vertex. At each turn, the flea decides to either jump to the left or to the right to the next (closest) vertex. The flea continues this movement until it has visited all vertices. Let $a_i$ be a sequence that records the flea's movement. If at $i$-th turn $(i \geq 1)$ the flea moves to the left then $a_i = -1$, and if it moves to the right then $a_i = 1$. We are told that this sequence is finite (i.e. the flea does visit all vertices and therefore stops). Show that there exists $j,k$ such that: $$| \sum_{i=j}^k a_i | = N-1$$

Students in a School

There are 3 schools, each of which has $n$ students. Each student knows altogether $n+1$ students from the other two schools. Prove that we can choose 3 students, each from a different school, such that they know each other.