Olimpiadas de Matemáticas
Página de preparación y problemas

Solución. Llamemos $a,b,c,d,e$ a las cifras del número ordenadas de decenas de millar a unidades. En los números de tres cifras formados con $a,b,c,d,e$, cada una de ellas aparece $12$ veces en las centenas, $12$ en las decenas y $12$ en las unidades ya que una vez fijado un dígito en una posición hay $4$ posibles elecciones en otra posición y, para cada una de ellas, $3$ en la última posición. Esto nos dice que la suma de los números de tres cifras distintas que se pueden formar con $a,b,c,d,e$ es igual a \[1200(a+b+c+d+e)+120(a+b+c+d+e)+12(a+b+c+d+e)=1332(a+b+c+d+e),\] donde el primer término (con coeficiente $1200$) viene de la suma de las centenas, el segundo (con coeficiente $120$) viene de las decenas y el último (con coeficiente $12$) de las unidades. Entonces, la condición del enunciado se reescribe equivalentemente como \[1332(a+b+c+d+e)=N=10000a+1000b+100c+10d+e.\qquad (\star)\] Como $1332$ es múltiplo de $9$, deducimos que $N$ es múltiplo de $9$, luego la suma $a+b+c+d+e$ también lo es. Esto nos dice que $N$ es múltiplo de $9\cdot 1332=11988$. Los únicos múltiplos de $11988$ menores que $100000$ que tienen todos sus dígitos distintos son \[\{23976,35964,47952,71928,83916\}\] y de ellos el único que cumple $(\star)$ es $N=35964$, luego esta es la única solución.

Solución. La ecuación se puede plantear de forma equivalente como \[(2x-1)(x-1)=y(y-3).\] Por tanto, si hay una solución $(x,y)$, deberá haber un número racional $r=\frac{p}{q}$ tal que $2x-1=ry$ y $x-1=\frac{y-3}{r}$. Este es un sistema que se puede resolver de forma única en términos de $r$ y nos queda \[x=\frac{r^2-r-3}{r^2-6}=\frac{p^2-3pq-3q^2}{p^2-6q^2},\qquad y=\frac{r-2}{r^2-6}=\frac{pq-2q^2}{p^2-6q^2}.\] Para cada solución $(p,q)$ de la ecuación $p^2-6q^2=1$, lo anterior nos da una solución entera $(x,y)$ de la ecuación original. Podemos daros cuenta de que $p^2-6q^2=1$ es una ecuación de Pell cuyo parámetro $D=6$ no es un cuadrado perfecto, luego tiene infinitas soluciones. No obstante, hay que asegurar que $x$ e $y$ son positivos y que las soluciones de Pell dan soluciones distintas de la ecuación original.

Una forma de obtener soluciones de la ecuación de Pell es la siguiente (ver la nota). Partimos de una solución concreta no trivial, por ejemplo, tomaremos $p_1=5$, $q_1=2$ (esta solución se encuentra tras probar un poco). Se tiene entonces una sucesión de soluciones $(p_n,q_n)$ tomando $p_n$ y $q_n$ como los únicos números naturales que verifican $(5+2\sqrt{6})^n=p_n+q_n\sqrt{6}$. Podemos desarrollar \[p_n+q_n\sqrt{6}=(5+2\sqrt{6})(p_{n-1}+q_{n-1}\sqrt{6})=(5p_{n-1}+12q_{n-1})+(2p_{n-1}+5q_{n-1})\sqrt{6},\]

lo que nos da la recurrencia \[\left\{\begin{array}{l}p_n=5p_{n-1}+12q_{n-1},\\q_n=2p_{n-1}+5q_{n-1}.\end{array}\right.\] También tenemos así una recurrencia para $r_n=\frac{p_n}{q_n}$ haciendo lo siguiente: \[r_n=\frac{p_n}{q_n}=\frac{5p_{n-1}+12q_{n-1}}{2p_{n-1}+5q_{n-1}}=\frac{5\frac{p_{n-1}}{q_{n-1}}+12}{2\frac{p_{n-1}}{q_{n-1}}+5}=\frac{5r_{n-1}+12}{2r_{n-1}+5}.\] La función $f(x)=\frac{5x+12}{2x+5}$ cumple que $f(x)=x$ si y solo si $x=\pm\sqrt{6}$. Teniendo en cuenta que $\lim_{x\to\infty}f(x)=\frac{5}{2}\gt \sqrt{6}$, es fácil ver que \[\sqrt{6}\lt x\lt f(x)\lt\frac{5}{2}\quad \text{para todo } x\gt\sqrt{6}.\] De esta manera, teniendo en cuenta que $r_1=\frac{p_1}{q_1}=\frac{5}{2}$, se sigue que $\sqrt{6}\lt r_{n-1}\lt r_n\leq\frac{5}{2}$ para todo $n\in\mathbb{N}$. Esto tiene dos consecuencias que resuelven el problema.

• En primer lugar, todos los $r_n$ son distintos, lo que nos dice que hay un número infinito de soluciones distintas al problema original. Esto es consecuencia de que $x$ e $y$ son funciones racionales de $r$ y una función racional no puede tomar el mismo valor para infinitos valores de la variable si no es idénticamente nula.
• En segundo y último lugar, las expresiones $\frac{r^2-r-3}{r^2-6}$ y $\frac{r-2}{r^2-6}$ son positivas para todo $r\gt \sqrt{6}$ luego todas nuestras soluciones $r_n$ hacen a $x$ e $y$ positivos.

Nota. Lo que hemos usado es que la ecuación de Pell $p^2-6q^2=1$ puede verse como números $p+q\sqrt{6}$ de norma $1$ en el anillo $\mathbb{Z}[\sqrt{6}]$. La norma de $a+b\sqrt{6}\in\mathbb{Z}[\sqrt{6}]$, con $a,b\in\mathbb{Z}$, se define de hecho como \[N(a+b\sqrt{6})=a^2-6b^2=(a+b\sqrt{6})\cdot(a-b\sqrt{6}).\] En realidad, se define como el valor absoluto de lo anterior, pero esto no es relevante para lo que vamos a decir porque lo interesante es que $N$ es multiplicativa, es decir, \[N((a+b\sqrt{6})(c+d\sqrt{6}))=N(a+b\sqrt{6})N(c+d\sqrt{6}).\] Desarrollando esta ecuación, simplemente estamos diciendo que lo siguiente se cumple para cualesquiera $a,b,c,d\in\mathbb{Z}$: \[(ac+6bd)^2-6(ad+bc)^2=(a^2-6b^2)(c^2-6d^2).\] Por lo tanto, si encontramos un número $a+b\sqrt{6}$ de norma $1$, todas sus potencias de exponente natural también tendrán norma $1$. Esto es lo que se ha usado en el problema.

Solución. Podemos desarrollar la potencia usando el binomio de Newton si escribimos la base como $2010-1$. Además, trabajaremos módulo $1000$ porque solo nos van a interesar las tres últimas cifras. Tenemos que \[2009^{2011}\equiv 9^{2011}\equiv(10-1)^{2011}\equiv-1+\binom{2011}{1}\cdot 2010-\binom{2011}{2}\cdot 10^2.\] No tenemos que poner más términos del binomio porque a partir del siguiente nos quedan múltiplos de $1000$. De esta forma, podemos seguir desarrollando módulo $1000$ los números combinatorios para escribir finalmente: \[2009^{2011}\equiv -1+11\cdot 10+55\cdot 10^2\equiv-391\equiv 609.\] Por lo tanto, las tres últimas cifras son $609$ y concluimos que solo hay un cero que precede al nueve.

Nota. Si necesitáramos más cifras sólo habría que trabajar módulo una potencia de \(10\) más grande y añadir más términos al desarrollo del binomio. Esto quiere decir que no es relevante en el problema que solo haya que calcular tres dígitos.

Solución. Vamos a trabajar módulo $1000$ ya que solo nos van a interesar las tres últimas cifras. Vamos a usar el teorema de Euler-Fermat que nos dice que $a^{\varphi(n)}\equiv 1\ (\text{mod }n)$ si $a$ y $n$ son primos relativos y $\varphi(n)$ es la función de Euler. En nuestro caso, pondremos $a=9$ y $n=1000$, usando que $\varphi(1000)=\varphi(2^3\cdot 5^3)=2^2(2-1)\cdot 5^2(5-1)=400$. Por lo tanto, \[2009^{2011}\equiv 9^{2011}=(9^{400})^5\cdot 9^{11}\equiv 9^{11}\ (\text{mod }1000).\] Ahora bien, este último resto lo podemos calcular, observando que \[9^2\equiv 81\ (\text{mod }1000),\quad 9^3\equiv 729\ (\text{mod }1000)\] para luego calcular rápidamente \[9^{11}\equiv 9^3\cdot 9^3\cdot 9^3\cdot 9^2\equiv 729\cdot 729\cdot 729\cdot 81\equiv 609\ (\text{mod }1000).\] Aunque pueda parecer una cuenta larga, sólo nos tenemos que quedar con las últimas tres cifras en cada paso. Deducimos así que las tres últimas cifras de $2009^{2011}$ son $609$, con lo que la respuesta a la pregunta del enunciado es uno.

Solución. Se pueden calcular algunos términos, pero rápidamente el resultado se dispara ya que la sucesión crece exponencialmente:\[x_1^2+1=5,\quad x_2^2+1=325,\quad x_3^2+1=136469125,\ldots\] Vamos a probar por inducción sobre $n$ que $x_n^2+1$ es múltiplo de $5^n$ pero no de $5^{n+1}$. Si probamos esto, tendremos que la solución al problema es $5^{2024}$. Está claro que el caso $n=1$ es cierto ya que $x_1^2+1=5$ es múltiplo de $5$ pero no de $25$. También es cierto si $n=2$ ya que $x_2^2+1=325$ es múltiplo de $25$ pero no de $125$. Supongamos que la propiedad es cierta para $n\geq 2$, lo que nos permite escribir $x_n^2+1=5^ny_n$, siendo $y_n$ no múltiplo de $5$. Entonces, para $x_{n+1}$ podemos desarrollar y simplificar \begin{align*}x_{n+1}^2+1&=(2x_n^3+x_n)^2+1=(4x_n^4+4x_n^2+1)x_n^2+1\\\\&=(4(5^ny_n-1)^2+4(5^ny_n-1)+1)(5^ny_n-1)+1\\\\&=4\cdot 5^{3n}y_n^3-8\cdot 5^{2n}y_n^2+5^{n+1}y_n\\\\&=5^{n+1}(4\cdot 5^{2n-1}y_n^3-8\cdot 5^{n-1}y_n^2+y_n).\end{align*}Este número es múltiplo de $5^{n+1}$ pero no de $5^{n+2}$ ya que el factor $4\cdot 5^{2n-1}y_n^3-8\cdot 5^{n-1}y_n^2+y_n$ es congruente con $y_n$ módulo $5$. Aquí estamos usando que $n\geq 2$ para asegurar que $5^{n-1}$ es múltiplo de $5$, es decir, en la inducción hemos tenido que comprobar dos casos iniciales.