36-я Балканская математическая олимпиада. Кишенёв, Молдова, 2019 год

Пусть $\mathbb{P}$ — множество всех простых чисел. Определите все функции $f: \mathbb{P} \to \mathbb{P}$ такие, что $f{(p)^{f(q)}} + {p^q} = f{(q)^{f(p)}} + {p^q}$ для всех $p, q \in \mathbb{P}$.

Комментарий/решение

Пусть $P(x,y)$ - данное равенство.

$P(2,q)\rightarrow f(2)^{f(q)}+q^2=f(q)^2+2^q$

При $q$ нечётном, получаем, что одно из чисел $f(q)$, $f(2)$ чётно. Предположим, что $f(2)$ - нечётное, тогда $f(p)=2$ для любого простого $p>2$.

$$p,q>2,P(p,q)\rightarrow p^q=q^p$$, что является противоречием.

Значит $f(2)=2$.

$P(2,p)\rightarrow 2^{f(p)}-f(p)^2=2^p-p^2$.

Докажем, что $g(x)=2^x-x^2$ строго возрастает для целых $x\ge3$. По методу математической индукции $2^x>2x+1$, откуда $g(x+1)-g(x)=2^x-2x-1>0$, что требовалось.

Следовательно $f(p)=p$ (ведь из нечётности $p,f(p)\ge3$)

$P(p,2)$ where $p\neq 2$: $$ f(p)^{f(2)}+2^p-f(2)^{f(p)}-p^{2}=0 $$

Consider this equation modular 2:

$$ f(p)^{f(2)}-f(2)^{f(p)}-p^2\equiv 0 $$

Suppose $f(p)\neq 2$ (one can easily verify that $f(p)=2$

is not a solution of the functional equation)

, then since $p\neq 2$, we have that:

$2|f(2)^{f(p)}$, hence $f(2)=2$. \\

Now $P(3,2)$:

$$ f(3)^2+2^3=2^{f(3)}+3^2 $$

$$ 2^{f(3)}=(f(3)+1)(f(3)-1) $$

So, $f(3)=3$. (\textbf{Assumption: $f(p)\geq p$, BUT

the argument is the same for $p\geq f(p)$}.)

Now, let's consider the largest

power of 2 that divides $f(p)-p$. Let $v_2(f(p)-p)=k$.

Notice that from we have

$$ f(p)^3-p^3=3^{f(p)}-3^p $$

Applying the Lifting the Exponent Lemma to (1.3):

$$v_2(f(p)^3-p^3)=v_2(f(p)-p)=k=v_2(3^p(3^{f(p)-p}-1))=$$

$$ =v_2(3-1)+v_2(3+1)+v_2(f(p)-p)-1=2+k $$

Hence, $k=k+2$ $\Longleftrightarrow$ $k=\infty$

$\Longleftrightarrow$ $f(p)-p=0$, $\forall p\in\mathbb{P}$,

as desired.

На самом деле задача имеет решение даже если область значения функции это любые натуральные числа.