Selectivo Cono Sur 2019 - P6

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial OFO - Medalla de Oro
Mensajes: 993
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Selectivo Cono Sur 2019 - P6

Mensaje sin leer por Gianni De Rico » Vie 29 Mar, 2019 3:23 pm

Ana y Beto juegan, por turnos, al siguiente juego. Inicialmente hay una pila con $n$ piedras. Cada jugador, en su turno, debe retirar un número de piedras mayor que $1$, que sea divisor del número total de piedras en la pila en el momento que le toca el turno, pero debe dejar por lo menos una piedra en la pila. El primer jugador que no puede realizar su jugada, pierde el juego. Ana juega en el primer turno. Hallar todos los enteros positivos $n$ para los que Ana puede desarrollar una estrategia que le asegure la victoria.
[math]

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial OFO - Medalla de Oro
Mensajes: 993
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Selectivo Cono Sur 2019 - P6

Mensaje sin leer por Gianni De Rico » Vie 29 Mar, 2019 9:59 pm

Spoiler: mostrar
Veremos que Ana tiene una estrategia ganadora si y sólo si $n$ es par.
Lo probaremos por inducción fuerte sobre $n$.
Como casos base tenemos $n=2$ y $n=3$. Para $n=2$, Ana saca una piedra, por lo que Beto recibe una pila de una piedra, entonces no puede jugar y pierde. Para $n=3$, como los únicos divisores de $3$ son $1$ y $3$, y Ana no puede sacar $3$ piedras (porque dejaría vacía la pila), debe sacar una piedra, entonces Beto recibe una pila de dos piedras y gana haciendo lo mismo que Ana en el caso anterior.
Supongamos como hipótesis inductiva que para todos los $n\leqslant 2k$, Ana tiene una estrategia ganadora si y sólo si $n$ es par. Veamos que esto vale para $2k+1$ y $2k+2$.
Como $2k+1$ es impar, no puede tener ningún divisor par, luego, todos sus divisores son impares, por lo tanto Ana saca $2x+1$ piedras de la pila (con $x\in \mathbb{N},x<k$), por lo que Beto recibe una pila con $2k+1-(2x+1)=2k-2x=2(k-x)$ piedras, que es un número par. Como Ana tiene una estrategia ganadora para todos los números pares, Beto puede aplicar esa estrategia y ganar. Por lo tanto, para $n=2k+1$ Ana no tiene una estrategia ganadora.
Para $n=2k+2$, Ana saca una piedra, entonces Beto recibe una pila de $2k+1$ piedras, y ya vimos que eso significa que Beto pierde, entonces Ana tiene una estrategia ganadora para $n=2k+2$. Esto completa la inducción.
1  
[math]

Heibor

OFO - Medalla de Bronce FOFO Pascua 2017 - Mención FOFO 7 años - Mención Especial
Mensajes: 18
Registrado: Mar 22 Sep, 2015 2:36 pm
Medallas: 4
Nivel: Exolímpico

Re: Selectivo Cono Sur 2019 - P6

Mensaje sin leer por Heibor » Vie 29 Mar, 2019 10:09 pm

"Debe retirar un número de piedras mayor que $1$"
Gianni De Rico escribió:
Vie 29 Mar, 2019 9:59 pm
Spoiler: mostrar
Veremos que Ana tiene una estrategia ganadora si y sólo si $n$ es par.
Lo probaremos por inducción fuerte sobre $n$.
Como casos base tenemos $n=2$ y $n=3$. Para $n=2$, Ana saca una piedra, por lo que Beto recibe una pila de una piedra, entonces no puede jugar y pierde. Para $n=3$, como los únicos divisores de $3$ son $1$ y $3$, y Ana no puede sacar $3$ piedras (porque dejaría vacía la pila), debe sacar una piedra, entonces Beto recibe una pila de dos piedras y gana haciendo lo mismo que Ana en el caso anterior.
Supongamos como hipótesis inductiva que para todos los $n\leqslant 2k$, Ana tiene una estrategia ganadora si y sólo si $n$ es par. Veamos que esto vale para $2k+1$ y $2k+2$.
Como $2k+1$ es impar, no puede tener ningún divisor par, luego, todos sus divisores son impares, por lo tanto Ana saca $2x+1$ piedras de la pila (con $x\in \mathbb{N},x<k$), por lo que Beto recibe una pila con $2k+1-(2x+1)=2k-2x=2(k-x)$ piedras, que es un número par. Como Ana tiene una estrategia ganadora para todos los números pares, Beto puede aplicar esa estrategia y ganar. Por lo tanto, para $n=2k+1$ Ana no tiene una estrategia ganadora.
Para $n=2k+2$, Ana saca una piedra, entonces Beto recibe una pila de $2k+1$ piedras, y ya vimos que eso significa que Beto pierde, entonces Ana tiene una estrategia ganadora para $n=2k+2$. Esto completa la inducción.

BrunZo

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

Re: Selectivo Cono Sur 2019 - P6

Mensaje sin leer por BrunZo » Vie 29 Mar, 2019 10:11 pm

Solución:
Spoiler: mostrar
Decimos que una posición (cantidad de fichas) es ganadora o perdedora si el primero que juega con esa cantidad gana o pierde, respectivamente.
Digo que $n$ es ganador si y sólo si $n$ es par pero no es una potencia impar de $2$. Lo demostraremos con inducción:
Es obvio que $n=1$ es perdedor. Ahora, supongamos que para todo $k<n$ se cumple lo dicho. Tenemos varios casos:

Caso i: $n$ es par pero no potencia de dos.
Claramente, $n$ tiene un divisor impar $d$. Luego, si se sacan $d$, quedan $n-d\equiv 1\mod 2$. Por hipótesis, esto es una posición perdedora, por lo que $n$ es ganador.

Caso ii: $n$ es potencia par de $2$.
Es claro que $2^{k-1}$ divide a $2^k$. Sacando eso, obtenemos $2^{k-1}$ que es perdedora (por ser potencia impar de $2$). Luego $n=2^k$ es ganadora.

Caso iii: $n$ es potencia impar de $2$.
Si $n=2^k$, es obvio que Ana deberá sacar $2^m$ con $1\leq m<k$. Luego, se obtendrá $2^k-2^m=2^m(2^{k-m}-1)$ que es par, pero no potencia impar de $2$ (si lo fuera, digamos que es $2^l$, $2^{k-m}=2\Longrightarrow l=m=k-1$, que es par). Luego, Ana pierde no importa lo que haga, o sea, $n$ es perdedor.

Caso iv: $n$ es impar.
Para $n$ primo, es obvio que Ana pierde. Desde ahora, $n$ es compuesto.
Supongamos que Ana toma un divisor $d_1$. Sea $d_2$ tal que $d_1d_2=n$. Es claro que $d_1$, $d_2$ son impares. Beto recibe $d_1d_2-d_1=d_1(d_2-1)$ que es par pero no potencia de $2$ (ya que $d_1>1$ es impar). Luego, Ana siempre pierde, o $n$ es perdedor.

Ahora, aplicando inducción fuerte, llegamos al resultado deseado.

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial OFO - Medalla de Oro
Mensajes: 993
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Selectivo Cono Sur 2019 - P6

Mensaje sin leer por Gianni De Rico » Vie 29 Mar, 2019 10:29 pm

Heibor escribió:
Vie 29 Mar, 2019 10:09 pm
"Debe retirar un número de piedras mayor que $1$"
Gianni De Rico escribió:
Vie 29 Mar, 2019 9:59 pm
Spoiler: mostrar
Veremos que Ana tiene una estrategia ganadora si y sólo si $n$ es par.
Lo probaremos por inducción fuerte sobre $n$.
Como casos base tenemos $n=2$ y $n=3$. Para $n=2$, Ana saca una piedra, por lo que Beto recibe una pila de una piedra, entonces no puede jugar y pierde. Para $n=3$, como los únicos divisores de $3$ son $1$ y $3$, y Ana no puede sacar $3$ piedras (porque dejaría vacía la pila), debe sacar una piedra, entonces Beto recibe una pila de dos piedras y gana haciendo lo mismo que Ana en el caso anterior.
Supongamos como hipótesis inductiva que para todos los $n\leqslant 2k$, Ana tiene una estrategia ganadora si y sólo si $n$ es par. Veamos que esto vale para $2k+1$ y $2k+2$.
Como $2k+1$ es impar, no puede tener ningún divisor par, luego, todos sus divisores son impares, por lo tanto Ana saca $2x+1$ piedras de la pila (con $x\in \mathbb{N},x<k$), por lo que Beto recibe una pila con $2k+1-(2x+1)=2k-2x=2(k-x)$ piedras, que es un número par. Como Ana tiene una estrategia ganadora para todos los números pares, Beto puede aplicar esa estrategia y ganar. Por lo tanto, para $n=2k+1$ Ana no tiene una estrategia ganadora.
Para $n=2k+2$, Ana saca una piedra, entonces Beto recibe una pila de $2k+1$ piedras, y ya vimos que eso significa que Beto pierde, entonces Ana tiene una estrategia ganadora para $n=2k+2$. Esto completa la inducción.
Se me pasó jajajaja. Teniendo eso en cuenta, mi solución quedaría idéntica a la de Bruno.
[math]

Responder