Selectivo de IMO 2021 - Problema 5

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Tomás Morcos Porras

COFFEE - Mención-COFFEE Matías Saucedo OFO - Mención-OFO 2020 COFFEE - Mención-COFFEE Iván Sadofschi FOFO 10 años - Mención-FOFO 10 años OFO - Medalla de Bronce-OFO 2021
OFO - Medalla de Bronce-OFO 2022
Mensajes: 202
Registrado: Dom 13 Oct, 2019 5:04 pm
Medallas: 6
Nivel: 3
Ubicación: Córdoba, Córdoba

Selectivo de IMO 2021 - Problema 5

Mensaje sin leer por Tomás Morcos Porras »

Consideramos la sucesión de números enteros $(x_n)$ tal que

$x_0=2$, $x_1=3$ y $x_{n+2}=7x_{n+1}-x_n+280$ para todo $n\geq 0$.

Demostrar que para todo entero positivo $n$ la suma de los divisores positivos del número $x_nx_{n+1}+x_{n+1}x_{n+2}+x_{n+2}x_{n+3}+626$ es divisible por $24$.
¿Mis intereses? Las várices de Winston Churchill.
Avatar de Usuario
joa.fernandez

FOFO 8 años - Mención Especial-FOFO 8 años OFO - Mención-OFO 2019 FOFO 9 años - Mención Especial-FOFO 9 años COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020
FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Copa-FOFO 10 años OFO - Medalla de Oro-OFO 2021 OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
OFO - Jurado-OFO 2023
Mensajes: 84
Registrado: Jue 20 Sep, 2018 9:40 pm
Medallas: 11
Nivel: Exolímpico

Re: Selectivo de IMO 2021 - Problema 5

Mensaje sin leer por joa.fernandez »

Lema:
Spoiler: mostrar
Si $24\mid n+1$, entonces la suma de los divisores positivos de $n$ es divisible por $24$.
Spoiler: mostrar
Sean $1=d_1<...<d_k=n$ los divisores de $n$. Notar que $d_id_{k+1-i}\equiv -1\pmod{24}$ de donde ese producto es congruente a $-1$ módulo $3$ y $8$.
Notar que si (como $d_i$ es coprimo con $3$) $d_i\equiv 1,-1\pmod{3}$, entonces necesariamente $d_{k+1-i}\equiv -1,1\pmod{3}$ respectivamente, de donde $d_i +d_{k+1-i}\equiv 0\pmod{3}$.
Análogamente (como $d_i$ es coprimo con $8$), si $d_i\equiv 1,3,5,7\pmod{8}$ se chequea a mano que $d_{k+1-i}\equiv -1,-3,-5,-7\pmod{8}$ respectivamente, de donde $d_i +d_{k+1-i}\equiv 0\pmod{8}$.
Además, notemos que siempre podemos agrupar las parejas, ya que $k$ debe ser par. En efecto, si fuera impar, entonces $n$ debería ser cuadrado perfecto, pero los restos cuadráticos módulo $3$ son $0,1$, y $n\equiv -1\pmod{3}$, absurdo.
Luego, la demo del lema queda completa.
Solución:
Spoiler: mostrar
Viendo la sucesión módulo $3$:
$$x_0\equiv 2,~x_1\equiv 0,~x_2\equiv 2,~x_3\equiv 0,~x_4\equiv 2,~x_5\equiv 0, ~\ldots~~~\pmod{3}$$
y como $x_{n+2}\equiv x_n$ para $n=0,1$, entonces la sucesión tiene ciclo de largo $2$.

En particular:
$$x_nx_{n+1}+x_{n+1}x_{n+2}+x_{n+2}x_{n+3}+626\equiv 2\equiv -1\pmod{3}$$ ya que alguno de los números $x_i$ o $x_{i+1}$ es congruente a $0$ módulo $3$ $\forall ~i \in \mathbb{Z}^+$.


Viendo la sucesión módulo $8$:
$$x_0\equiv 2,~x_1\equiv 3,~x_2\equiv 3,~x_3\equiv 2,~x_4\equiv 3,~x_5\equiv 3, ~\ldots~~~\pmod{8}$$
y como $x_{n+3}\equiv x_n$ para $n=0,1,2$, entonces la sucesión tiene ciclo de largo $3$.

En particular:
$$x_nx_{n+1}+x_{n+1}x_{n+2}+x_{n+2}x_{n+3}+626\equiv 3\cdot 3 + 2\cdot 3 + 2\cdot 3 + 4\equiv 15\equiv -1\pmod{8}$$ ya que siempre tomamos exactamente un producto de dos $3$'s consecutivos y dos productos de $2$ por $3$.

Pero, como $x_nx_{n+1}+x_{n+1}x_{n+2}+x_{n+2}x_{n+3}+626\equiv -1 \pmod{3}, \pmod{8}$, y $3$ y $8$ son coprimos, entonces $$x_nx_{n+1}+x_{n+1}x_{n+2}+x_{n+2}x_{n+3}+626\equiv -1\pmod{24}$$ de donde por el lema podemos demostrar lo pedido, completando la solución.
2  
Rotohomotecias como estilo de vida
Avatar de Usuario
Sandy

OFO - Medalla de Bronce-OFO 2019 OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Copa-FOFO 10 años
OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años OFO - Medalla de Plata-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 280
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 11
Nivel: 3

Re: Selectivo de IMO 2021 - Problema 5

Mensaje sin leer por Sandy »

joa.fernandez escribió: Vie 16 Abr, 2021 10:10 pm Lema:
Spoiler: mostrar
Si $24\mid n+1$, entonces la suma de los divisores positivos de $n$ es divisible por $24$.
Spoiler: mostrar
Sean $1=d_1<...<d_k=n$ los divisores de $n$. Notar que $d_id_{k+1-i}\equiv -1\pmod{24}$ de donde ese producto es congruente a $-1$ módulo $3$ y $8$.
Notar que si (como $d_i$ es coprimo con $3$) $d_i\equiv 1,-1\pmod{3}$, entonces necesariamente $d_{k+1-i}\equiv -1,1\pmod{3}$ respectivamente, de donde $d_i +d_{k+1-i}\equiv 0\pmod{3}$.
Análogamente (como $d_i$ es coprimo con $8$), si $d_i\equiv 1,3,5,7\pmod{8}$ se chequea a mano que $d_{k+1-i}\equiv -1,-3,-5,-7\pmod{8}$ respectivamente, de donde $d_i +d_{k+1-i}\equiv 0\pmod{8}$.
Además, notemos que siempre podemos agrupar las parejas, ya que $k$ debe ser par. En efecto, si fuera impar, entonces $n$ debería ser cuadrado perfecto, pero los restos cuadráticos módulo $3$ son $0,1$, y $n\equiv -1\pmod{3}$, absurdo.
Luego, la demo del lema queda completa.
Solución:
Spoiler: mostrar
Viendo la sucesión módulo $3$:
$$x_0\equiv 2,~x_1\equiv 0,~x_2\equiv 2,~x_3\equiv 0,~x_4\equiv 2,~x_5\equiv 0, ~\ldots~~~\pmod{3}$$
y como $x_{n+2}\equiv x_n$ para $n=0,1$, entonces la sucesión tiene ciclo de largo $2$.

En particular:
$$x_nx_{n+1}+x_{n+1}x_{n+2}+x_{n+2}x_{n+3}+626\equiv 2\equiv -1\pmod{3}$$ ya que alguno de los números $x_i$ o $x_{i+1}$ es congruente a $0$ módulo $3$ $\forall ~i \in \mathbb{Z}^+$.


Viendo la sucesión módulo $8$:
$$x_0\equiv 2,~x_1\equiv 3,~x_2\equiv 3,~x_3\equiv 2,~x_4\equiv 3,~x_5\equiv 3, ~\ldots~~~\pmod{8}$$
y como $x_{n+3}\equiv x_n$ para $n=0,1,2$, entonces la sucesión tiene ciclo de largo $3$.

En particular:
$$x_nx_{n+1}+x_{n+1}x_{n+2}+x_{n+2}x_{n+3}+626\equiv 3\cdot 3 + 2\cdot 3 + 2\cdot 3 + 4\equiv 15\equiv -1\pmod{8}$$ ya que siempre tomamos exactamente un producto de dos $3$'s consecutivos y dos productos de $2$ por $3$.

Pero, como $x_nx_{n+1}+x_{n+1}x_{n+2}+x_{n+2}x_{n+3}+626\equiv -1 \pmod{3}, \pmod{8}$, y $3$ y $8$ son coprimos, entonces $$x_nx_{n+1}+x_{n+1}x_{n+2}+x_{n+2}x_{n+3}+626\equiv -1\pmod{24}$$ de donde por el lema podemos demostrar lo pedido, completando la solución.
Una demo del lema sin separar en casos (créditos a @Brunzo):
Spoiler: mostrar
$d_i+d_{k+1-i}=d_i+\frac{-1}{d_i}=\frac{d_i^2-1}{d_i}$.
Pero $d_i$ es coprimo con $24$, y es fácil ver (chequear) que, para todo coprimo con $24$, su cuadrado es $1$ módulo $24$. Luego, al ser $d_i$ y $24$ coprimos, $\frac{d_i^2-1}{d_i}\equiv 0(24)$. Como $-1$ no es residuo cuadrático módulo $24$, cada divisor de $n$ tiene su pareja distinta a sí mismo.
1  
Fallo inapelable.
Responder