1. We call polynomials $A(x)=a_{n} x^{n}+\ldots+a_{1} x+a_{0}$ and $B(x)=b_{m} x^{m}+\ldots+b_{1} x+b_{0}$ $\left(a_{n} b_{m} \neq 0\right)$ similar if the following conditions hold:

(i) $n=m$;

(ii) There is a permutation $\pi$ of the set $\{0,1, \ldots, n\}$ such that $b_{i}=a_{\pi(i)}$ for each $i \in\{0,1, \ldots, n\}$.

Let $P(x)$ and $Q(x)$ be similar polynomials with integer coefficients. Given that $P(16)=3^{2012}$, find the smallest possible value of $\left|Q\left(3^{2012}\right)\right|$.

(Miloš Milosavljević)
1. Since $3^{2012} \equiv 1(\bmod 5)$, it holds that $Q\left(3^{2012}\right) \equiv Q(1)=P(1) \equiv P(16) \equiv 1$ $(\bmod 5)$, so $\left|Q\left(3^{2012}\right)\right| \geqslant 1$.

Now we construct polynomials $P$ and $Q$ satisfying the conditions for which $Q\left(3^{2012}\right)=1$. Set $P(x)=a x^{2}+b x+c$ and $Q(x)=c x^{2}+a x+b$. Denoting $m=16$ and $n=3^{2012}$, we want the system of equations

$$
\left\{\begin{array}{r}
a m^{2}+b m+c=n \\
c n^{2}+a n+b=1
\end{array}\right.
$$

to have an integer solution $(a, b, c)$. Substituting $c=n-a m^{2}-b m$ in the second equation yields $n^{2}\left(n-a m^{2}-b m\right)+a n+b=1$, i.e. $n\left(m^{2} n-1\right) a+\left(m n^{2}-1\right) b=n^{3}-1$, so it suffices that this equation have an integer solution $(a, b)$. The last condition is equivalent to $\operatorname{gcd}\left(n\left(m^{2} n-1\right), m n^{2}-1\right) \mid n^{3}-1$, which is true: Indeed, if $d \mid n\left(m^{2} n-1\right)$ and $d \mid m n^{2}-1$, then $d \mid n\left(m^{2} n-1\right)-m\left(m n^{2}-1\right)=m-n$, and therefore $d \mid m n^{2}-1+n^{2}(n-m)=n^{3}-1$.

Second solution. As in the first solution, $Q\left(3^{2012}\right) \neq 0$.

In order to achieve that $Q\left(3^{2012}\right)=1$, knowing that $P\left(3^{2012}\right) \equiv Q\left(3^{2012}\right)$ $\left(\bmod 3^{2012}-1\right)$, we impose the extra condition $P\left(3^{2012}\right)=P(16)=3^{2012}$. The polynomial $P$ is of the form $P(x)=(x-16)\left(x-3^{2012}\right) S(x)+3^{2012}$. Suppose that $S$ is chosen in such a way that $P(x)=a_{n} x^{n}+\cdots+a_{2} x^{2}+(c+1) x+c$ for some $c \in \mathbb{Z}$; then taking $Q(x)=a_{n} x^{n}+\cdots+a_{2} x^{2}+c x+(c+1)$ would yield precisely $Q\left(3^{2012}\right)=P\left(3^{2012}\right)-\left(3^{2012}-1\right)=1$.

We find $S(x)$ in the form $a x+b$. The last two coefficients in $P(x)$ are $16 \cdot 3^{2012} a-$ $\left(16+3^{2012}\right) b$ and $16 \cdot 3^{2012} b+3^{2012}$ respectively. Thus it suffices to take $a$ and $b$ so that $16 \cdot 3^{2012} a-\left(16 \cdot 3^{2012}+16+3^{2012}\right) b-3^{2012}=1$, which is possible because $16 \cdot 3^{2012}$ and $16 \cdot 3^{2012}+16+3^{2012}$ are coprime.