Nacional 2019 N1 P1

Problemas que aparecen en el Archivo de Enunciados.
LuchoLP

OFO - Medalla de Bronce OFO - Medalla de Plata
Mensajes: 191
Registrado: Mié 17 Abr, 2013 7:27 pm
Medallas: 3
Nivel: Exolímpico

Nacional 2019 N1 P1

Mensaje sin leer por LuchoLP » Jue 14 Nov, 2019 9:56 am

Los tres enteros $2000$, $19$ y $n$ están escritos en el pizarrón. Ana y Beto juegan el siguiente juego:
Comienza Ana y luego juegan por turnos. Cada jugada consiste en borrar uno de los números del pizarrón y reemplazarlo por la diferencia de los otros dos (el mayor menos el menor). Solo están permitidas las jugadas en las que se modifica uno de los números escritos. El jugador que en su turno no puede jugar, pierde.
Demostrar que para todo valor de $n$, el juego tiene un ganador y determinar quién gana si los números del pizarrón son $2000$, $19$ y $2019$.

BrunZo

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

Re: Nacional 2019 N1 P1

Mensaje sin leer por BrunZo » Sab 16 Nov, 2019 6:55 pm

Solución:
Spoiler: mostrar
Asumamos que $n$ es positivo, ya que si no el problema no tiene sentido.
Supongamos que luego de la primera jugada resultan los números $x$, $y$ y $x-y$. Si escribimos $a=x-y$, $b=y$, podemos escribir a los tres números como
$$a,\quad b,\quad a+b$$
Sin pérdida de generalidad, $a\leq b\leq a+b$. Si $a=b=0$ el juego ya terminó.
Vamos a probar que: o bien $a=0$, o bien al hacer una jugada, el mayor de los tres números decrece:
Si $a=0$ resulta inmediato: Asumamos $a>0$. Es claro que cambiar $a$ por $(a+b)-b$ o cambiar $b$ por $(a+b)-a$ no son jugadas válidas, por lo que lo único válido es que resulten
$$a,\quad b,\quad a-b$$
Queda bien claro que como $b>a>0$ entonces $a-b<a+b$, $a<a+b$ y $b<a+b$, por lo que efectivamente el mayor de los tres números nuevos es menor que $a+b$, de modo que decreció.
Para finalizar, notemos que si $a=0$, entonces $(a,b,a+b)=(a,0,a)$, por lo que el juego termina. Si $a>0$, podemos hacer que el mayor de los tres números decrezca hasta que o bien este se vuelva no positivo ($a=b=0$), o bien $a=0$, con lo que el juego también termina, como se nos pedía demostrar.

Para la segunda parte (dejo sólo la idea), como $2000+19=2019$, cada jugada está determinada, por lo que basta cuántas operaciones hay hasta llegar a $(0,0,x)$ y se termina esta parte.

Martín Lupin
Mensajes: 10
Registrado: Lun 20 May, 2019 10:26 am
Nivel: 1
Ubicación: Mar del Plata

Re: Nacional 2019 N1 P1

Mensaje sin leer por Martín Lupin » Lun 18 Nov, 2019 2:45 pm

Solución:
Spoiler: mostrar
Si $n\neq 1981$, entonces siempre gana Ana. En el primer turno, Ana elige borrar $n$ y reemplazarlo por $1981$ (si $n=2019$, Ana está obligada a hacer esta jugada). Luego Beto está obligado a borrar $2000$ y reemplazarlo por $1962$. Después Ana está obligada a borrar $1981$ y reemplazarlo por $1943$. En todos los turnos posteriores, los jugadores estarán obligados a borrar cierto número del pizarrón. Nótese que en los turnos pares juega Beto y el primer número decrece en $38$, y que en los turnos impares juega Ana el tercer número decrece también en $38$. Luego podemos establecer una forma general de los números escritos en el pizarrón en el turno $k$:
$2000-\left\lfloor\frac{k}{2}\right\rfloor\cdot 38,\quad 19,\quad 2019-\left\lfloor\frac{k+1}{2}\right\rfloor\cdot 38$
En el turno $k=105$, los números son $24, 19, 5$. Aquí por primera vez el tercer número es menor al segundo, por lo que nuestra fórmula ya no es válida. Estas son las jugadas que siguen: $14, 19, 5\to 14, 9, 5\to 4, 9, 5\to 4, 1, 5\to 4, 1, 3\to 2, 1, 3\to 2, 1, 1\to 0, 1, 1$. Ahora viene el turno de Beto ya que es el turno 114 (el cual es par), pero no puede borrar ningún número ya que $0=1-1$ y $1=1-0$, por lo que no puede seguir jugando y gana Ana.
En el caso $n=1981$, las jugadas son las mismas que si $n\neq 1981$, pero las jugadas que realizaba Ana ahora las realiza Beto y viceversa, por lo que en este caso gana Beto, y así queda demostrado que siempre hay un ganador.

Responder