Página 1 de 1

1er Selectivo Cono Sur 2019 Uruguay - Problema 1

Publicado: Sab 31 Ago, 2019 9:27 pm
por Sandy
$A$ y $B$ juegan con un montón de $2019$ fichas, por turnos.
En cada turno se permite quitar una cantidad de fichas que sea divisor de la cantidad de fichas del montón.
Pierde quien quita la última ficha.
Si $A$ juega primero, ¿quién tiene estrategia ganadora?

Re: 1er Selectivo Cono Sur Uruguay - Problema 1

Publicado: Sab 31 Ago, 2019 9:43 pm
por Gianni De Rico

Re: 1er Selectivo Cono Sur Uruguay - Problema 1

Publicado: Sab 31 Ago, 2019 10:04 pm
por Sandy
Gianni De Rico escribió: Sab 31 Ago, 2019 9:43 pm Provincial 2014 N1 P2
Incluso la generalización es el 6 de SelCono de Argentina de este año

Re: 1er Selectivo Cono Sur 2019 Uruguay - Problema 1

Publicado: Dom 23 Ago, 2020 5:31 am
por Tomás Morcos Porras
Este era el problema que resolví, pero Sandy me hizo confundir. (?)
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_{2019}$. 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). $2019$ es impar, $B$ tiene estrategia ganadora.