Problema 3, IMO 2010

Primero demostremos que $g$ tiene que ser inyectiva. Esto es, $g(n)=g(m)$ si y sólo si $n=m$.

Supongamos que $g(n)=g(m) = N$, entonces para todo entero $a$ se tiene que: $$(N+a)(n+g(a)) \quad \textrm{y} \quad (N+a)(m+g(a))\quad  \textrm{ son cuadrados}$$

Pero podemos encontrar $a$ tal que $N+a=p$ es un número primo. En tal caso, para que las expresiones de arriba sean cuadrados será necesario (mas no suficiente) que $p$ divida a $n+g(a)$ y también a $m+g(a)$. Entonces, $p$ debe dividir a la diferencia, es decir, $p| (n-m)$. Pero como hay una infinidad de tales primos $p$ (de la forma N+a), entonces, $n-m = 0$ pues es el único entero que tiene una infinidad de divisores. Es decir, hemos demostrado que $n=m$.

Como $g$ es inyectividad, entonces  $|g(n)-g(n+1)| \geq 1$. Supongamos que $|g(n)-g(n+1)| \geq 2$, por lo que existe un primo $p$ divisor de $|g(n)-g(n+1)|$, es decir, $g(n) \equiv g(n+1) \pmod{p}$.  Para poder continuar demostremos el siguiente lema:

Lema. 1 Si $a \equiv  b \pmod{p}$ con $p$ primo, entonces existe un entero $c$ tal que, tanto $a+c$  como $b+c$ tienen en su descomposición prima a $p$ elevado a una potencia impar.

Demostración:
Claramente existe un $c_0$ tal que $a+c_0$  y $b+c_0$ son enteros positivos divisibles por $p$. Es decir, $a+c_0=p\alpha$  y $b+c_0=p\beta$.

Supongamos ahora que $p \geq 3$. Por lo que, los tres residuos $0, 1, 2$ son diferentes. Entonces, para alguno de estos residuos $r \in \{0,1,2\}$,  $\alpha +r$ y $\beta+r$ no son divisibles por $p$. Entonces, para $c= c_0 + pr$ los números $a+c$ y $b+c$ son divisibles por $p$ pero no por $p^2$. Esto es, en la descomposición prima de ambos $p$ aparece con exponente 1.

Ahora sólo nos falta considerar el caso en que $p = 2$. En este caso,  usaremos módulo 8. De esta manera tendremos más residuos, y sólo basta con encontrar un residuo $r$ tal que tanto $\alpha+r$ como $\beta +r$  sean  congruentes copn $1,3, 4, 5 o 7 \pmod{8}$ y ya habremos terminado. Pues esto implica que $\alpha + r$ (al igual que $\beta +r$) es impar o bien, divisible por 4 pero no por 8. Con esta $r$ definimos $c= c_0 + 2r$ y ya está.

 Una vez probado el lema 1, podemos afirmar que existe $c$ tal que $g(n)+c$ y $g(n+1)+c$  tienen en su descomposición prima a $p$ elevado a una potencia impar. Pero como $$(g(n)+c)(n+g(c)) \quad \textrm{y} \quad (g(n+1)+c)(n+1+g(c)) \quad \textrm{son cuadrados}$$ entonces, también $n+g(c)$ y $n+1+g(c)$ deben tener a $p$ elevado a una potencia impar en su descomposición primo, en particular, $p$ debe dividir a ambos. Pero $n+g(c)$ y $n+1+g(c)$ son primos relativos, lo que contradice que $p$ divide a ambos.  Por lo que la hipotesis de que $|g(n)-g(n+1)| \geq 2$ es falsa.

Ahora bien, hemos demostrado que  $|g(n)-g(n+1)| =1$ y que $g$ es inyectiva. Entonces, $g$ debe cambiar de valor de uno en uno,  es decir, $g(n+1) = g(n) \pm 1$.  Pero no puede ocurrir que en dos número consecutivos, esta fórmula, sufra un cambio de signo (en el $\pm$), es decir, $$\g(n+1) = g(n) \pm 1 \quad \textrm{y} \quad g(n+2) = g(n+1) \mp 1.$$  

Pues al sumar ambas ecuaciones y reducir tendremos que $g(n+2) =g(n+1)$, contradiciendo la inyectividad. Por último, $g(n+1) = g(n) -1$ para todo $n \in \mathbb{N}$, no podría ser pues en $\mathbb{N}$ no se puede decrecer al infinito. Por lo tanto, $g(n+1) = g(n) +1$ para toda $n \in \mathbb{N}$, esto es equivalente a que $g(n) = n + c$ con $c$ una constante en $\mathbb{N}$.

Solución adaptada de Problems – Beni Bogoşel