EGMO 2021 - P1

Problemas que aparecen en el Archivo de Enunciados.
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
Mensajes: 254
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 6
Nivel: 3

EGMO 2021 - P1

Mensaje sin leer por Sandy »

El número $2021$ es fantabuloso. Si para algún entero positivo $m$, alguno de los elementos $\{m,2m+1,3m\}$ es fantabuloso, entonces totos los elementos de dicho conjunto son fantabulosos. ¿Esto significa que el número $2021^{2021}$ es fantabuloso?
Fallo inapelable.

Avatar de Usuario
enigma1234

OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2020 - Copa-FOFO Pascua 2020
Mensajes: 110
Registrado: Sab 03 Jun, 2017 8:07 pm
Medallas: 4
Nivel: 2

Re: EGMO 2021 - P1

Mensaje sin leer por enigma1234 »

Spoiler: mostrar
Lema 1: Para todo entero positivo $n$, $n$ es fantabuloso $\iff 2n$ es fantabuloso y $n$ es fantabuloso $\iff 2n+1$ es fantabuloso.
Prueba:
Spoiler: mostrar
Claramente tenemos que $n$ es fantabuloso $\iff 2n+1$ es fantabuloso para todo entero positivo $n$.
  • Tomando $m=2n$ tenemos que $2n$ es fantabuloso $\iff 2(2n)+1=4n+1$ es fantabuloso.
  • Tomando $m=4n+1$ tenemos que $4n+1$ es fantabuloso $\iff 3(4n+1)=12n+3$ es fantabuloso.
  • Tomando $m=6n+1$ tenemos que $2(6n+1)+1=12n+3$ es fantabuloso $\iff 6n+1$ es fantabuloso.
  • Tomando $m=3n$ tenemos que $2(3n)+1=6n+1$ es fantabuloso $\iff 3n$ es fantabuloso.
  • Tomando $m=n$ tenemos que $3n$ es fantabuloso $\iff n$ es fantabuloso.
Luego claramente obtenemos que el lema es cierto.

Lema 2: El menor entero positivo fantabuloso es $1$.

Prueba:
Spoiler: mostrar
Como $2021$ es fantabuloso, luego existe un mínimo, digamos $a$, $a\geq 1$.

Supongamos que $a>1$, luego por el lema 1, $1\leq \lfloor \frac{a}{2}\rfloor<a$ es fantabuloso, contradiciendo la minimalidad.

Por lo tanto $a=1.$
Lema 3: Todos los enteros positivos son fantabulosos.
Spoiler: mostrar
Prueba: Veamos que esto es cierto por inducción fuerte. Tenemos que $1$ es fantabuloso por el Lema 2. Supongamos que los números del $1$ al $n$ son fantabulosos.

Como $1\leq \lfloor\frac{n+1}{2}\rfloor\leq n$, entonces $\lfloor\frac{n+1}{2}\rfloor$ es fantabuloso y por el Lema 1, $n+1$ es fantabuloso, con lo que la inducción esta completa.
Por lo tanto todos los enteros positivos son fantabulosos, en particular $2021^{2021}$ es fantabuloso.

Avatar de Usuario
Monazo

OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Mención-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021
Mensajes: 317
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 12
Nivel: Ñandú

Re: EGMO 2021 - P1

Mensaje sin leer por Monazo »

Básicamente, la solución es la misma que @enigma1234, pero con un remate distinto.
Spoiler: mostrar

Como muy bien está demostrado en la solución de arriba, si se puede para cualquiera de estos $3$ valores: $\{n,\ 2n,\ 2n + 1\}$, entonces se puede para los $3$.

El remate distinto, es que ahora podemos pensar en binario. Dada la representación en binario de un número, gracias a la propiedad de arriba, yo puedo realizar cualquiera de estas $3$ operaciones:

$\bullet$ Eliminar el último dígito de la representación en binario, sin importar si es un $1$ o un $0$.
$\bullet$ Agregar un dígito $1$ al final de la representación en binario. (Aplicar la operación $n \implies 2n+1$)
$\bullet$ Agregar un dígito $0$ al final de la representación en binario. (Aplicar la operación $n \implies 2n$)

De esta manera, notemos que aplicando siempre la primera operación, podemos llegar a tener finalmente un $1$, y luego, vemos la representación en binario de $2021^2$, y en cada momento vemos que nos conviene, si aplicar la segunda o la tercera operación, porque si logramos que sus representaciones en binario sean iguales, entonces el número en decimal será el mismo también. De esta manera, podemos definir el camino para llegar desde un número a cualquier otro que deseamos.
2  
El Diego es del Lobo! Y del Lobo no se va!

Responder