1. For the 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} \quad\left(a_{n} b_{m} \neq 0\right)$, we say they are similar if the following conditions hold:

(i) $n=m$;

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

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

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

We will construct polynomials $P$ and $Q$ that satisfy the conditions of the problem and for which $Q\left(3^{2012}\right) = 1$. We seek polynomials in the form $P(x) = a x^{2} + b x + c$ and $Q(x) = c x^{2} + a x + b$. For $m = 16$ and $n = 3^{2012}$, we need 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 at least one integer solution $(a, b, c)$. By substituting $c = n - a m^{2} - b m$ into the second equation, we get $n^{2}(n - a m^{2} - b m) + a n + b = 1$, i.e., $n(m^{2} n - 1) a + (m n^{2} - 1) b = n^{3} - 1$; it is sufficient that this equation has an integer solution $(a, b)$, and this will happen if and only if $\gcd(n(m^{2} n - 1), m n^{2} - 1) \mid n^{3} - 1$. We will show that this is true: if $d \mid n(m^{2} n - 1)$ and $d \mid m n^{2} - 1$, then $d \mid n(m^{2} n - 1) - m(m n^{2} - 1) = m - n$, and from there $d \mid m n^{2} - 1 + n^{2}(n - m) = n^{3} - 1$.

Second solution. The proof that $Q\left(3^{2012}\right) \neq 0$ is conducted as in the first solution.

To achieve $Q\left(3^{2012}\right) = 1$, and knowing that $P\left(3^{2012}\right) \equiv Q\left(3^{2012}\right) \pmod{3^{2012} - 1}$, we impose the condition $P\left(3^{2012}\right) = P(16) = 3^{2012}$. The polynomial $P$ is of the form $P(x) = (x - 16)(x - 3^{2012}) S(x) + 3^{2012}$. If we can choose the polynomial $S$ such that

\[
P(x) = a_{n} x^{n} + \cdots + a_{2} x^{2} + (c + 1) x + c
\]

for some $c \in \mathbb{Z}$, then by taking $Q(x) = a_{n} x^{n} + \cdots + a_{2} x^{2} + c x + (c + 1)$, we get exactly $Q\left(3^{2012}\right) = P\left(3^{2012}\right) - (3^{2012} - 1) = 1$.

We seek the polynomial $S(x)$ in the form $a x + b$. The last two coefficients in $P(x)$ are $16 \cdot 3^{2012} a - (16 + 3^{2012}) b$ and $16 \cdot 3^{2012} b + 3^{2012}$. It is sufficient to choose $a$ and $b$ such that $16 \cdot 3^{2012} a - (16 \cdot 3^{2012} + 16 + 3^{2012}) b - 3^{2012} = 1$, and this is possible because $16 \cdot 3^{2012}$ and $16 \cdot 3^{2012} + 16 + 3^{2012}$ are coprime.