FOFO 9+1 Años - Problema 3

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Luli97

OFO - Mención-OFO 2015 OFO - Medalla de Bronce-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 2017 FOFO 7 años - Jurado-FOFO 7 años
OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-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
Mensajes: 142
Registrado: Mar 16 Abr, 2013 8:23 pm
Medallas: 17
Nivel: Exolímpico

FOFO 9+1 Años - Problema 3

Mensaje sin leer por Luli97 »

Mili y Lola juegan el siguiente juego por turnos. Empieza Mili, escribiendo una permutación de los números del $1$ a $n$, con $n$ entero positivo fijo mayor que $1$. En su turno, cada jugadora escribe una secuencia de números que no haya sido escrita todavía tal que se cumpla alguna de las siguientes dos condiciones:
  • $\mathbf{(a)}$ La secuencia es una permutación de la secuencia que escribió la jugadora en el turno anterior.
  • $\mathbf{(b)}$ La secuencia se obtiene al eliminar un número de la secuencia que escribió la jugadora en el turno anterior.
Por ejemplo, si Mili escribe $4123$, Lola puede escribir $3124$ o $413$. La jugadora que no pueda escribir una secuencia pierde. Determinar, para cada $n$, que jugadora tiene estrategia ganadora.

Avatar de Usuario
Luli97

OFO - Mención-OFO 2015 OFO - Medalla de Bronce-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 2017 FOFO 7 años - Jurado-FOFO 7 años
OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-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
Mensajes: 142
Registrado: Mar 16 Abr, 2013 8:23 pm
Medallas: 17
Nivel: Exolímpico

Re: FOFO 9+1 Años - Problema 3

Mensaje sin leer por Luli97 »

Solución oficial
Spoiler: mostrar
Veamos primero qué pasa cuando $n=2$. En este caso, comienza Mili escribiendo alguna de las permutaciones de los números $1,2$, es decir, $1-2$ o $2-1$. En cualquiera de los dos casos Lola puede eliminar el número $2$, escribiendo la única permutación de un número que es $1$. Así, Mili se quedará sin movimientos por hacer y perderá.

Ahora, si $n>2$, comienza Mili escribiendo una permutación de los números del $1$ al $n$.
Veamos que Lola tiene la estrategia ganadora sin importar el valor de $n$.

Observación importante: $k!$ que es la cantidad de permutaciones de $k$ elementos es par si $k\geq 2$.

Si se escribieron varias permutaciones de $n$ elementos y le toca jugar a Lola, entonces escribieron una cantidad impar de permutaciones porque se alternaron turnos y Mili jugó una vez más que Lola (pues escribió la primera y la última permutación hasta el momento). Esto quiere decir, que seguro que Lola puede escribir otra permutación con la misma cantidad de números, pues la cantidad de permutaciones es par.

Así, ya sea porque se acabaron las permutaciones de $n$ elementos o porque Mili decida hacer en algún momento una operación de tipo $(b)$, Lola puede asegurarse que no será ella (será Mili) la que escriba la primera permutación de $n-1$ elementos.

Por lo tanto, vamos disminuyendo la cantidad de números que tienen las permutaciones escritas y si Lola sigue el procedimiento que describimos arriba, se asegura que será Mili la que escriba la primera permutación en cada caso: Mili escribe la primera permutación con $n$ números, después la primera con $n-1$ números, luego la de $n-2$ números y así siguiendo. Eventualmente, Mili escribirá una permutación con $2$ elementos, Lola quitará uno de ellos y quedará escrita una permutación de $1$ elemento, lo que hará que Mili no tenga operaciones para hacer.

De esta forma podemos afirmar que Lola tiene la estrategia ganadora, para todo valor de $n>2$.

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
Mensajes: 68
Registrado: Jue 20 Sep, 2018 9:40 pm
Medallas: 7
Nivel: 3

Re: FOFO 9+1 Años - Problema 3

Mensaje sin leer por joa.fernandez »

Solución:
Spoiler: mostrar
Veamos que gana Lola.
Si $n=2$, Mili juega alguna permutación de $1$, $2$; Lola quita alguno de los dos números y gana.
Para $n>2$, Mili juega una permutación de los números del $1$ al $n$, (y teniendo en cuenta que estas permutaciones son en total $n!$), Lola tiene para jugar $n!-1$ permutaciones, que es impar para $n>1$. Notemos que la paridad de la cantidad de permutaciones que puede jugar Lola, si Mili no quita ningún número, no cambia, y como en un principio es $1$, siempre podrá jugar alguna permutación.
Luego, la estrategia de Lola siempre será jugar alguna permutación. Eventualmente Mili deberá quitar uno de los números. En ese momento, al ser $n-1$ números distintos, se tienen $(n-1)!$ permutaciones y como Mili ya escribió alguna de esas permutaciones, Lola tiene $(n-1)! -1$ permutaciones disponibles para jugar. Nuevamente notamos que la paridad de esta no cambia si no se quita ningún número. Análogamente, vemos que en algún momento Mili deberá sacar algún número y Lola siempre podrá jugar una permutación sin necesidad de sacarlo. Entonces, eventualmente Mili escribirá en el pizarrón $2$ números distintos, $a$ y $b$, donde Lola puede sacar $a$ y asegurarse siempre la victoria para todo $n>1$.

Responder