Математикадан 51-ші халықаралық олимпиада, 2010 жыл, Астана

$\mathbb{N}$ арқылы барлық оң бүтін сандар жиынын белгілейік. $(g(m)+n)(m+g(n))$ саны кез келген $m,n\in \mathbb{N}$ үшін қандай-да бір бүтін санның квадраты болатындай барлық $g:\mathbb{N}\to \mathbb{N}$ функцияларын табыңыз.

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

Предположим существует такое простое $p$, что $p|g(n+1)-g(n)$. Легко видеть, что существует такое $k$, что $v_p(g(n+1)+k)=v_p(g(n)+k)=1$. Поскольку $(g(n)+k)(g(k)+n)$ является точным квадратом $p|g(k)+n$. Аналогично $p|g(k)+n+1$, откуда $p|1$ - противоречие. Поэтому $g(n+1)-g(n)=\pm1$. Если $g(n+1)=g(n)-1$, то $(g(n)+n+1)(g(n+1)+n)=(g(n)+n)^2-1$ является полным квадратом - противоречие. В итоге $g(n+1)=g(n)+1$, значит $g(n)=n+C$ для некоторой постоянной $C$, а это подходит.

а что, если $p=2, g(n+1)=0(mod$ $4), g(n) = 2(mod$ $4)?$ Тогда ведь не существует такого $k$.

Ох! Действительно. При $p>2$ это верно, но не при $p=2$. К счастью, данную дыру легко залатать. При $g(n+1)\equiv g(n)\pmod4$ такое $k$ найдётся. Значит $g(n+1)=g(n)\pm2$. Случай $g(n+1)=g(n)+2$ простой. Если $g(n)=g(n+1)+2$, то $$(g(n)+n+1)(g(n+1)+n)=(g(n+1)+n+3)(g(n+1)+n)$$ квадрат, то есть $x(x+3)$ квадрат для $x=g(n+1)+n\ge2$. Это невозможно. При $x$ не делящихся на 3 мы имеем, что $x,x+3$ взаимно просты, то бишь они оба являются квадратами - противоречие для $x>1$. При $x=3s$ выходит, что $s(s+1)$ квадрат - также невозможно

Также $g(n+1) \ne g(n)$ в силу инъективности. Она доказывается следующим образом:

Пусть $g(a)=g(b), a \ne b$ тогда возьмем такое $n$, чтобы $g(a)+n \in P$. Тогда $P(a,n)$:

$$(g(a)+n)(a+g(n) = x^2;$$

$$(g(b)+n)(b+g(n) = y^2$$

Тогда $a+g(n)$ делится на $p, b+g(n)$ делится на $p$, то есть $a-b$ делится на $p$, хотя $p$ можно взять сколь угодно большим, противоречие.

P.S. случай $g(n+1)=g(n)$ разбирать необязательно, оказывается