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

Solución. Descomponemos los números del $1$ al $100$ en $10$ subconjuntos disjuntos de $10$ elementos cada uno, de acuerdo a la última cifra decimal. Ahora bien, como estamos eligiendo $55$ números, de alguno de estos subconjuntos tomaremos al menos $6$ por el principio del palomar. Esto asegura que al menos dos de ellos tendrán la cifra de las unidades consecutiva (sólo hay $10$ cifras de las decenas posibles) y estos dos números difieren exactamente en $10$ unidades.

Vamos a ver que la misma idea nos da el contraejemplo a elegir cuando la diferencia es de $11$ unidades. Para ello, descomponer los números entre $1$ y $100$ en $11$ subconjuntos según su resto módulo $11$. Estos subconjuntos son: \begin{align*} \{11,22,33,44,55,66,77,88,99\},&\quad\text{que tiene }9\text{ elementos,}\\ \{1,12,23,34,45,56,67,78,89,100\},&\quad\text{que tiene }10\text{ elementos,}\\ \{2,13,24,35,46,57,68,79,90\},&\quad\text{que tiene }9\text{ elementos,}\\ \qquad\vdots&\\ \{10,21,32,43,54,65,76,87,98\},&\quad\text{que tiene }9\text{ elementos.} \end{align*} Sólo uno de los subconjuntos tiene $10$ elementos y en él elegimos los números $1,23,45,67,89$. En los otros $10$ subconjuntos (que tienen todos $9$ elementos), elegimos los números que ocupan la posición primera, tercera, quinta, séptima y novena. De esta forma, hemos elegido un total de $55$ elementos ($5$ en cada subconjunto) de forma que no hay dos de ellos que se diferencien en $11$ unidades.

Nota. Con ideas similares, se puede ver que debe haber dos números cuya diferencia sea $9$ unidades, dos cuya diferencia sea $12$ unidades y dos cuya diferencia sea $13$ unidades.

Solución. Escribamos por simplicidad $x_n=(1+\sqrt{5})^n+(1-\sqrt{5})^n$. Vamos a probar el resultado por inducción completa sobre $n$. El caso base $n=1$ (en realidad, para $n=0$ también es válido si se quiere incluir), nos da $x_1=(1+\sqrt{5})+(1-\sqrt{5})=2$, que es un entero divisible entre $2$. Supongamos entonces que $x_k$ es un entero divisible entre $2^k$ para todo $k\leq n$. Para analizar el siguiente número $x_{n+1}$, hacemos el siguiente desarrollo \begin{align*} 2x_n&=[(1+\sqrt{5})+(1-\sqrt{5})][(1+\sqrt{5})^n+(1-\sqrt{5})^n]\\ &=(1+\sqrt{5})^{n+1}+(1-\sqrt{5})^{n+1}+(1+\sqrt{5})(1-\sqrt{5})^n+(1-\sqrt{5})(1+\sqrt{5})^n\\ &=x_{n+1}+(1+\sqrt{5})(1-\sqrt{5})x_{n-1}=x_{n+1}-4x_{n-1} \end{align*} Podemos así despejar $$x_{n+1}=2x_n+4x_{n-1}=2\cdot 2^n\cdot a+4\cdot 2^{n-1}\cdot b=2^{n+1}(a+b),$$ para ciertos enteros $a$ y $b$, donde hemos usado por hipótesis de inducción que existen dichos enteros tales que $x_n=2^n\cdot a$ y $x_{n-1}=2^{n-1}\cdot b$. Deducimos así que $x_{n+1}$ es un múltiplo de $2^{n+1}$ y hemos terminado la demostración.

Nota. Sabiendo un poco sobre sucesiones recurrentes lineales, el número $x_n=\alpha^n+\beta^n$ verifica una recurrencia lineal $x_{n+1}=p x_n+qx_{n-1}$, siendo $\alpha$ y $\beta$ las raíces del polinomio $x^2-px-q=0$.

Solución. Procedamos por inducción sobre $n$. Para el caso base $n=1$, se cumple la igualdad: $$\binom{2n}{n}=\binom{2}{1}=2=\frac{4}{2}=\frac{4^n}{n+1}.$$ Supongamos entonces que la desigualdad es cierta para $n$ y veamos qué ocurre para $n+1$. Usando la hipótesis de inducción, tenemos que \begin{align*} \binom{2(n+1)}{n+1}&=\frac{(2n+2)!}{((n+1)!)^2}=\frac{(2n+2)(2n+1)(2n)!}{(n+1)^2(n!)^2}=\frac{2(2n+1)}{n+1}\binom{2n}{n}>\frac{(2n+1)4^{n+1}}{(n+1)^2}. \end{align*} Ahora sólo falta ver que $\frac{2n+1}{(n+1)^2}\geq\frac{1}{n+2}$, lo que equivale a que $(2n+1)(n+2)\geq (n+1)^2$, esto es, $n^2+n+1\geq 0$. Ya hemos terminado porque esta última igualdad es claramente cierta (es la suma de tres números positivos).

Como la desigualdad $n^2+n+1\gt 0$ es realmente estricta, deducimos que no puede haber igualdad para ningún $n\geq 2$, luego la igualdad se alcanza sólo para $n=1$.

Solución. Vamos a probar la fórmula por inducción sobre $n$. El caso base es $n=1$, para el que se tiene que el miembro de la izquierda es \begin{align*} \frac{1}{x-1}-\frac{4}{x^4-1}&=\frac{1}{x-1}-\frac{4}{(x-1)(x+1)(x^2+1)}=\frac{(x+1)(x^2+1)-4}{(x-1)(x+1)(x^2+1)}\\ &=\frac{x^3+x^2+x-3}{(x-1)(x+1)(x^2+1)}=\frac{x^2+2x+3}{(x+1)(x^2+1)}\\ &=\frac{(x^2+1)+2(x+1)}{(x+1)(x^2+1)}=\frac{1}{x+1}+\frac{2}{x^2+1} \end{align*} Supongamos ahora que la igualdad es cierta para $n-1$, es decir, supongamos que $$\frac{1}{x+1}+\frac{2}{x^2+1}+\frac{4}{x^4+1}+\ldots+\frac{2^{n-1}}{x^{2^{n-1}}+1}=\frac{1}{x-1}-\frac{2^{n}}{x^{2^{n}}-1}.$$ Entonces, para el siguiente caso tenemos que \begin{align*} \frac{1}{x+1}+\ldots+\frac{2^n}{x^{2^n}+1}&=\frac{1}{x-1}-\frac{2^{n}}{x^{2^{n}}-1}+\frac{2^n}{x^{2^n}+1}\\ &=\frac{1}{x-1}-\frac{2^n[(x^{2^{n}}-1)-(x^{2^{n}}+1)]}{(x^{2^{n}}-1)(x^{2^n}+1)}=\frac{1}{x-1}-\frac{2^{n+1}}{x^{2^{n+1}}-1}, \end{align*} donde hemos aplicado la hipótesis de inducción a los primeros $n$ sumandos.

Solución. Que los tres últimos dígitos coincidan equivale a que $$1978^n-1978^m=1978^m(1978^{n-m}-1)\equiv 0\ (\text{mod }1000).$$ Esto implica que $m\geq 3$ ya que $1000=2^35^3$ y nos bastará trabajar módulo $5^3=125$. Vamos a buscar, por tanto, el menor entero $k$ tal que $1978^k\equiv 1\ (\text{mod }125)$. El teorema de Euler-Fermat nos dice que $1978^{\varphi(125)}\equiv 1\ (\text{mod }125)$ ya que $\mathrm{mcd}(125,1978)=1$, siendo $\varphi(125)=5^2(5-1)=100$. El menor exponente $k$ que estamos buscando debe ser un divisor de $100$ (ver nota), lo que nos da las posibilidades $k=1,2,4,5,10,20,25,50,100$. Ahora bien, como $1978\equiv 103\ (\text{mod }125)$, tenemos que $$1978^{2}\equiv 103^2=10609\equiv 109\ (\text{mod }125),\quad 1978^4\equiv 109^2=11881\equiv 6\ (\text{mod }125),$$ luego podemos calcular $$1978^{20}\equiv 103^4(103^4)^4=6\cdot 6^4\equiv 6\cdot 36^2\equiv 6\cdot 46\equiv 26\ (\text{mod }125).$$ Esto nos dice que el $k$ buscado no es igual a ninguno de los números $1,2,3,4,10,20$ (divisores de $20$). Probemos ahora $k=50$, lo que nos permitirá descartar también $25$ y $50$: $$1978^{50}\equiv 103^2((103^4)^4)^3=109\cdot 46^3\equiv 109\cdot 86\equiv 124\ (\text{mod }125).$$ Esto nos deja sólo la posibilidad $k=100$, que nos da $m=3$ y $n=103$. Por tanto, la menor suma posible es $m+n=106$.

Nota. La afirmación de que $k$ debe ser un divisor de $100$ es un hecho conocido, pero vamos a demostrarlo. Si tomamos $d=\mathrm{mcd}(k,100)$, entonces la identidad de Bézout nos dice que existen $u$ y $v$ tales que $d=ku+100v$, luego $1978^d=(1978^k)^u(1978^{100})^v\equiv 1\ (\text{mod }125$. Si $k$ es el menor entero positivo que cumple $1978^k\equiv 1\ (\text{mod }125)$, entonces tiene que ser $d=k$, es decir, $k$ es un divisor de $100$.