FOFO 12 Años - Problema 1

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 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 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
Mensajes: 2015
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 14
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

FOFO 12 Años - Problema 1

Mensaje sin leer por Gianni De Rico »

Un saltamontes se encuentra al inicio de un camino de $2022$ metros que conduce a su casa. Para llegar a ella el saltamontes va a ir realizando saltos hacia adelante de manera que la longitud de cada salto sea una cantidad entera (no nula) de metros y que en cada salto recorra una distancia mayor que en el salto anterior.
¿Cuántos saltos realizó el saltamontes para llegar a su casa? Dar todas las posibilidades.
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 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 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
Mensajes: 2015
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 14
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: FOFO 12 Años - Problema 1

Mensaje sin leer por Gianni De Rico »

Solución Oficial:
Spoiler: mostrar
Primero que nada, como en cada salto el saltamontes avanza una cantidad entera de metros y avanza más que en el salto anterior, entonces si en un salto avanzó $k$ metros, en el siguiente debe avanzar al menos $k+1$ metros.
En el primer salto avanza al menos un metro, en el segundo salto avanza al menos dos metros, y así siguiendo, en el salto número $k$ avanza al menos $k$ metros (si uno quiere puede hacer inducción para probar esto). Entonces en $n$ saltos avanza al menos $1+2+\cdots +n=\dfrac{n(n+1)}{2}$ metros. Probando un poco (o resolviendo la cuadrática $\dfrac{n(n+1)}{2}=2022$) encontramos que con $n=64$ el saltamontes avanza al menos $\dfrac{64\cdot(64+1)}{2}=2080$ metros, de modo que se pasa de su casa. Si hace más de $64$ saltos también se pasa. Entonces el saltamontes puede llegar a su casa únicamente realizando entre $1$ y $63$ saltos. Falta ver que todas las opciones son posibles.
Para llegar en $63$ saltos hace un salto de $1$ metro, un salto de $2$ metros, y así va aumentando en $1$ metro cada salto hasta que llega a $62$ metros, finalmente realiza un salto de $69$ metros, que anda porque $1+2+\cdots +62+69=2022$. Si llegó en $k$ saltos puede llegar en $k-1$ saltos haciendo los dos últimos saltos juntos. Por ejemplo, para llegar en $62$ saltos hace un salto de $1$ metro, un salto de $2$ metros, y así va aumentando en $1$ metro cada salto hasta que llega a $61$ metros, finalmente, realiza un salto de $62+69$ metros; para llegar en $61$ saltos hace saltos de longitudes $1$, $2$, $\ldots$, $60$ metros y un salto de $61+62+69$ metros. Esto funciona siempre porque el último salto mide al menos $69$ metros y los demás miden a lo sumo $62$ metros.
Entonces el saltamontes puede haber realizado entre $1$ y $63$ saltos para llegar a su casa.
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850
usuario250

OFO - Jurado-OFO 2015
Mensajes: 222
Registrado: Vie 30 Dic, 2011 12:30 pm
Medallas: 1

Re: FOFO 12 Años - Problema 1

Mensaje sin leer por usuario250 »

Consulta, cuán complejo sería el problema de determinar la cantidad de posibilidades en que el saltamontes haga los saltos para cada una de las posibles cantidades de saltos?
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 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 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
Mensajes: 2015
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 14
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: FOFO 12 Años - Problema 1

Mensaje sin leer por Gianni De Rico »

Este comentario es para avisar que ya está publicada la solución oficial.
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850
Responder