FOFO de Pascua 2019 Problema B: ¿No son Ana y Beto?

Avatar de Usuario
Chino2000

OFO - Medalla de Plata FOFO 7 años - Medalla Especial FOFO 8 años - Jurado OFO - Jurado FOFO Pascua 2019 - Jurado
Mensajes: 36
Registrado: Mar 09 Dic, 2014 10:18 pm
Medallas: 6
Nivel: 1

FOFO de Pascua 2019 Problema B: ¿No son Ana y Beto?

Mensaje sin leer por Chino2000 » Jue 18 Abr, 2019 12:00 am

En el pizarrón están escritos los primeros $1025$ enteros no negativos: $0,1,2,3,\ldots,1024$. Por turnos Mario y Luigi juegan al siguiente juego. Inicialmente Mario elige $2^9$ números del pizarrón y los borra, luego Luigi elige $2^8$ números del pizarrón y los borra, y así siguiendo hasta que por último Luigi borra $2^0$ números y quedan solo $2$ números en el pizarrón. Luigi deberá pagarle a Mario la diferencia (positiva) en pesos de estos dos números. Hallar la máxima cantidad de dinero que Mario puede asegurarse ganar.

Avatar de Usuario
Chino2000

OFO - Medalla de Plata FOFO 7 años - Medalla Especial FOFO 8 años - Jurado OFO - Jurado FOFO Pascua 2019 - Jurado
Mensajes: 36
Registrado: Mar 09 Dic, 2014 10:18 pm
Medallas: 6
Nivel: 1

Re: FOFO de Pascua 2019 Problema B: ¿No son Ana y Beto?

Mensaje sin leer por Chino2000 » Dom 21 Abr, 2019 11:36 pm

Aquí vamos a publicar la solución oficial.

BrunZo

OFO - Medalla de Bronce FOFO 8 años - Mención Especial OFO - Medalla de Plata FOFO Pascua 2019 - Medalla
Mensajes: 112
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 4
Nivel: 1

Re: FOFO de Pascua 2019 Problema B: ¿No son Ana y Beto?

Mensaje sin leer por BrunZo » Lun 22 Abr, 2019 3:21 pm

Solución:
Spoiler: mostrar
Llamemos $N$ al número buscado.

Supongamos que Mario, en cada uno de sus pasos, saca los números en posición par (ordenados de menor a mayor). En cada punto, tenemos en cuenta la menor diferencia entre números. Vamos a demostrar que en cada movimiento de Mario, esta, al menos, se duplica:
Supongamos que la menor diferencia es $d$. Tomemos un número eliminado. Como $d$ es mínima, este número tendrá diferencia mayor o igual a $d$ con cada uno de sus dos consecutivos (en el orden de menor a mayor), por lo que, la diferencia estos dos números será mayor o igual que $2d$. Aplicado a todos los números eliminados, vemos que la distancia entre cualesquiera dos números consecutivos después de la eliminación es, al menos, $2d$, con lo que estamos.
Ahora, como Mario hace cinco movimientos, finalmente, todas las difernecias serán mayores a $32$, o sea, $N\geq 32$.

Ahora, supongamos que Luigi, en cada uno de sus movimientos, elimina los primeros o los últimos números. En cada punto, tenemos en cuenta la diferencia entre los números extremos (menor y mayor). Vamos a demostrar que en cada paso, Luigi puede asegurarse de que esta diferencia, como mucho, se divida a la mitad:
Sea $D$ la diferencia inicial. Luego del movimiento de Luigi, sabemos que los números de los extremos pueden ser: el menor y el central (llamemos $D_1$), o el central y el mayor (digamos $D_2$). Es claro que $D=D_1+D_2$, luego el menor de $D_1$, $D_2$ será, como mucho, $\frac{D}{2}$.
Entonces, es claro que después de los cinco pasos de Luigi, finalmente, todas las diferencias serán menores o iguales a $32$, o sea, $N\leq 32$.

De este modo, concluímos que $N=32$.
2  

Responder