Selectivo Cono Sur 2019 - P6

Problemas que aparecen en el Archivo de Enunciados.
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 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Selectivo Cono Sur 2019 - P6

Mensaje sin leer por Gianni De Rico »

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.
♪♫ do re mi función lineal ♪♫
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 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Selectivo Cono Sur 2019 - P6

Mensaje sin leer por Gianni De Rico »

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  
♪♫ do re mi función lineal ♪♫
Heibor

OFO - Medalla de Bronce-OFO 2016 OFO - Medalla de Bronce-OFO 2017 FOFO Pascua 2017 - Mención-FOFO Pascua 2017 FOFO 7 años - Mención Especial-FOFO 7 años
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 »

"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-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Copa-FOFO 10 años OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años
OFO - Medalla de Oro-OFO 2022 FOFO Pascua 2022 - Medalla-FOFO Pascua 2022 FOFO 12 años - Medalla-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 414
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 16
Nivel: 3

Re: Selectivo Cono Sur 2019 - P6

Mensaje sin leer por BrunZo »

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-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 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Selectivo Cono Sur 2019 - P6

Mensaje sin leer por Gianni De Rico »

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.
♪♫ do re mi función lineal ♪♫
Avatar de Usuario
Tomás Morcos Porras

COFFEE - Mención-COFFEE Matías Saucedo OFO - Mención-OFO 2020 COFFEE - Mención-COFFEE Iván Sadofschi FOFO 10 años - Mención-FOFO 10 años OFO - Medalla de Bronce-OFO 2021
OFO - Medalla de Bronce-OFO 2022
Mensajes: 202
Registrado: Dom 13 Oct, 2019 5:04 pm
Medallas: 6
Nivel: 3
Ubicación: Córdoba, Córdoba

Re: Selectivo Cono Sur 2019 - P6

Mensaje sin leer por Tomás Morcos Porras »

Spoiler: mostrar
Llamo $p_j$ a la piedra en la j-ésima posición, tal que la piedra al fondo de la pila es $p_1$ y la de arriba del todo $p_n$. Además, llamo ganadoras o perdedoras a las piedras que garantizan victoria o derrota respectivamente a quien empiece su turno en ellas.
Lema 1: Sea $p_x$ perdedora. Luego, como de $p_{x+1}$ se puede llegar a $p_x$ sacando $1$ piedra, $p_{x+1}$ es ganadora.
Lema 2: Sea $p_i$ una piedra con $i$ impar y sean todas las piedras $p_{i-1}$, $p_{i-3}$, $p_{i-5}$ ... $p_2$ ganadoras. Luego, como todos los divisores de $i$ son impares, todo movimiento posible deja al rival en posición ganadora y $p_i$ es perdedora.
Por último, vemos que $p_1$ pierde y $p_2$ gana. De ahí, por los lemas 1 y 2, todas las piedras en posiciones impares son perdedoras y todas las piedras en posiciones pares son ganadoras (véase que si todas las piedras $p_{i-1}$, $p_{i-3}$, $p_{i-5}$ ... $p_2$ son ganadoras, y $p_i$ es perdedora, entonces $p_{i+1}$ es también ganadora y $p_{i+2}$ es también perdedora). $n$ tiene que ser par.
¿Mis intereses? Las várices de Winston Churchill.
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 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Selectivo Cono Sur 2019 - P6

Mensaje sin leer por Gianni De Rico »

Tomás Morcos Porras escribió: Sab 22 Ago, 2020 11:41 pm
Spoiler: mostrar
Lema 1: Sea $p_x$ perdedora. Luego, como de $p_{x+1}$ se puede llegar a $p_x$ sacando $1$ piedra, $p_{x+1}$ es ganadora.
Se te pasó el mismo dato que a mí, la cantidad de piedras que se sacan es mayor que $1$.
♪♫ do re mi función lineal ♪♫
Avatar de Usuario
Tomás Morcos Porras

COFFEE - Mención-COFFEE Matías Saucedo OFO - Mención-OFO 2020 COFFEE - Mención-COFFEE Iván Sadofschi FOFO 10 años - Mención-FOFO 10 años OFO - Medalla de Bronce-OFO 2021
OFO - Medalla de Bronce-OFO 2022
Mensajes: 202
Registrado: Dom 13 Oct, 2019 5:04 pm
Medallas: 6
Nivel: 3
Ubicación: Córdoba, Córdoba

Re: Selectivo Cono Sur 2019 - P6

Mensaje sin leer por Tomás Morcos Porras »

Gianni De Rico escribió: Sab 22 Ago, 2020 11:56 pm Se te pasó el mismo dato que a mí, la cantidad de piedras que se sacan es mayor que $1$.
...Oh. A pensarlo de vuelta se ha dicho.
¿Mis intereses? Las várices de Winston Churchill.
Avatar de Usuario
Tomás Morcos Porras

COFFEE - Mención-COFFEE Matías Saucedo OFO - Mención-OFO 2020 COFFEE - Mención-COFFEE Iván Sadofschi FOFO 10 años - Mención-FOFO 10 años OFO - Medalla de Bronce-OFO 2021
OFO - Medalla de Bronce-OFO 2022
Mensajes: 202
Registrado: Dom 13 Oct, 2019 5:04 pm
Medallas: 6
Nivel: 3
Ubicación: Córdoba, Córdoba

Re: Selectivo Cono Sur 2019 - P6

Mensaje sin leer por Tomás Morcos Porras »

Y se ha pensado de vuelta.
Spoiler: mostrar
Creo que llegué básicamente a la solución de @BrunZo, pero con inducción débil.


Llamo $p_j$ a la piedra en la j-ésima posición, tal que la piedra al fondo de la pila es $p_1$ y la de arriba del todo $p_{n}$. Además, llamo ganadoras o perdedoras a las piedras que garantizan victoria o derrota respectivamente a quien empiece su turno en ellas.
Primero veamos que los primos pierden porque sacar los divisores implica un movimiento ilegal (sacar $1$ o sacar todas).
Luego, $p_2$, $p_3$, $p_5$ y $p_7$ son perdedoras porque son posiciones de números primos. De ahí, se sigue que $p_4$ y $p_6$ son ganadoras y $8$ es perdedora porque $8-4=4$ y $8-2=6$ son ambas ganadoras.

Asumamos que hay una piedra $p_\gamma$ tal que entre $p_2$ y $p_\gamma$ pierden todas las impares y las potencias impares de $2$, y gana el resto.
Si $p_\gamma=p_{2^\alpha}$ es potencia impar de $2$, es perdedora: Todos sus divisores son pares, entonces restarle cualquiera a $2^\alpha$ resulta en par. El par más chico resulta $2^{\alpha-1}$, que es potencia par de $2$ y todas las pares entre medio, contándola, son ganadoras.
Ahora, si $p_\gamma$ es $p_i$ con $i$ impar no primo, también es perdedora: Todos los divisores de $i$ son impares $f$ y su diferencia par, o sea que, o $i-f=2^\alpha$ para algún $\alpha$ impar o $i-f=2\times \beta$ para algún beta entero que no es potencia par de $2$. Veamos que el primer caso es imposible: $2^\alpha+f\equiv i \pmod{f}\implies2^\alpha\equiv 0\pmod{f}$, pero vimos que $f$ era impar, absurdo. Entonces, todas las diferencias entre $i$ y sus divisores darán par ganadora.
Por último, si $p_\gamma$ es $p_q$ con $q$ par no potencia impar de $2$, es ganadora: Dividir a $q$ la mayor cantidad de veces posible sin que deje de ser entero resulta en un divisor impar perdedora o en $1$, en cuyo caso $\frac{q}{2}$ es una potencia impar de $2$ perdedora.

Ya vimos que se cumple para $p_\gamma$ hasta $8$ (con lógica booleana hacía falta hasta $4$, pero a nadie le gustaría eso) , queda demostrado de ahí para arriba. Las posiciones ganadoras de $n$ son los números pares exceptuando a las potencias impares de $2$.
¿Mis intereses? Las várices de Winston Churchill.
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 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Selectivo Cono Sur 2019 - P6

Mensaje sin leer por Gianni De Rico »

Tomás Morcos Porras escribió: Dom 23 Ago, 2020 8:52 am Y se ha pensado de vuelta.
Spoiler: mostrar
Creo que llegué básicamente a la solución de @BrunZo, pero con inducción débil.
Spoiler: mostrar
En realidad, usaste inducción fuerte, que es suponer que se cumple para todos los anteriores ($k\leqslant n$). Inducción común es suponer únicamente que se cumple para $k=n-1$.

De todos modos, te faltaría explicar por qué funcionan un par de los casos. Por ejemplo, mostrar por qué restando un divisor de una potencia impar de $2$, no podés llegar a una potencia impar de $2$. O mostrar cuál es el paso que tiene que hacer Ana para llegar a una posición perdedora cuando tiene una potencia par de $2$.
♪♫ do re mi función lineal ♪♫
Responder