IMO-Auswahlklausur

Solution:

1st Solution: Define the polynomial $P(x)=x^{3}-36 x^{2}+51 x-97$. Starting from $P_{0}(x)=\frac{1}{81} P(9 x+1)=9 x^{3}-33 x^{2}-2 x-1$, define recursively polynomials $P_{k}(x)=3 a_{k} x^{3}+3 b_{k} x^{2}+c_{k} x+d_{k}$ with integers $a_{k}, b_{k}, c_{k}, d_{k}$, where $c_{k}$ is not divisible by 3, and $P_{k+1}(x)=\frac{1}{3} P_{k}\left(3 x+\varepsilon_{k}\right)$ with $\varepsilon_{k} \in\{-1,0,1\}$ for all $k$: Since $c_{k}$ is not divisible by 3, one can choose $\varepsilon_{k}$ such that $\varepsilon_{k} c_{k}+d_{k}$ is divisible by 3; then $\frac{1}{3} P_{k}\left(3 x+\varepsilon_{k}\right)=3 a_{k+1} x^{3}+3 b_{k+1} x^{2}+c_{k+1} x+d_{k+1}$ with $a_{k+1}=9 a_{k}, b_{k+1}=9 \varepsilon_{k} a_{k}+3 b_{k}$, $c_{k+1}=3\left(3 \varepsilon_{k}^{2} a_{k}+2 \varepsilon_{k} b_{k}\right)+c_{k}, d_{k+1}=\varepsilon_{k}^{3} a_{k}+\varepsilon_{k}^{2} b_{k}+\left(\varepsilon_{k} c_{k}+d_{k}\right) / 3$, so $c_{k+1}$ is also not divisible by 3.
Setting $x_{2004}=0$ and recursively $x_{k}=3 x_{k+1}+\varepsilon_{k}$, i.e. $P_{k}\left(x_{k}\right)=3 P_{k}\left(x_{k+1}\right)$ for $k=2003, \ldots, 0$, then for $a=9 x_{0}+1$ the number $P(a)=81 \cdot 3^{2004} P_{2004}\left(x_{2004}\right)$ is a multiple of $3^{2008}$.

2nd Solution: Define the polynomial $P(x)=x^{3}-36 x^{2}+51 x-97$. For $k \geq 4$, integers $a_{k}$ with $a_{k} \equiv 1 \bmod 9$ and $3^{k} \mid P\left(a_{k}\right)$ are constructed inductively; the problem statement is then satisfied by $a=a_{2008}$:
Base case $k=4$: For $a_{4}=1$ we have $3^{4} \mid P\left(a_{4}\right)$.
Induction step $k \rightarrow k+1$: For $k \geq 4$ we have $2 k-3 \geq k+1$ and $3 k-6>k+1$, so for
all integer $x$:

$$\begin{aligned} P\left(x+3^{k-2}\right)-P(x) & \equiv 3^{k-1} x^{2}+3^{2 k-3} x+3^{3 k-6}-36\left(2 \cdot 3^{k-2} x+3^{2 k-4}\right)+51 \cdot 3^{k-2} \\ & \equiv 3^{k-1}\left(x^{2}-24 x+17\right) \bmod 3^{k+1} \end{aligned}$$

For $x \equiv 1 \bmod 9$ we have $x^{2}-24 x+17 \equiv 1-24+17 \equiv 3 \bmod 9$. Because $k \geq 4$ we also have $x \equiv x+3^{k-2} \bmod 9$. Therefore the difference $3^{k-1}\left(x^{2}-24 x+17\right)$ contains the prime factor 3 exactly $k$ times, so $P(u)$ is divisible by $3^{k+1}$ for $u=a_{k}$ or $u=a_{k}+3^{k-2}$ or $u=a_{k}+2 \cdot 3^{k-2}$; set $a_{k+1}$ to this value of $u$. By construction $a_{k+1} \equiv 1 \bmod 9$.