Selectivo IMO 2019 - Problema 2

[jujumas]

Inicialmente en el pizarrón están escritos los enteros desde $1$ hasta $100$ inclusive. La operación permitida es elegir dos números del pizarrón, $a$ y $b$, escribir en el pizarrón el máximo común divisor de $a^2b^2+3$ y $a^2+b^2+2$, y borrar $a$ y $b$. Se realizan operaciones permitidas hasta que en el pizarrón queda un solo número. Demostrar que este número no puede ser un cuadrado perfecto.

[BrunZo]

Solución:

Spoiler: mostrar

Si $a$ y $b$ no son múltiplos de $3$, o son ambos múltiplos de $3$, sabemos que $a^2+b^2+2$ va a tener restos $1$ ó $2$ módulo $3$, respectivamente. De este modo, la operación no deja un múltiplo de $3$.
Ahora, si sólo uno de ellos es múltiplo de $3$, ambos $a^2b^2+3$ y $a^2+b^2+2$ lo serán, por lo que la operación dejará un múltiplo de $3$.
De este modo, sabemos que la cantidad de múltiplos de $3$ es invariante módulo $2$, y como hay $33$ al principio, el último número deberá ser múltiplo de $3$.
Esto implica que si $x$ e $y$ eran los dos últimos números, sólo uno de ellos era múltiplo de $3$, con lo que $x^2y^2+3\equiv 3\mod 9$, por lo que el último número no podrá ser múltiplo de $9$. Pero, un múltiplo de $3$ que no es múltiplo de $9$ no puede ser cuadrado perfecto, y con eso estamos.