Problema 5 Selectivo de IMO 2000

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

Colaborador OFO - Jurado
Mensajes: 562
Registrado: Dom 17 Oct, 2010 10:28 pm
Medallas: 3
Nivel: Exolímpico

Problema 5 Selectivo de IMO 2000

Mensaje sin leer por Nacho » Jue 26 Jul, 2012 6:50 pm

Juan y Pablo juegan, por turnos, al siguiente juego: cada uno, en su turno, escribe un número natural que sea divisor positivo de [math] y que no haya sido escrito antes. Después de cada jugada, se calcula el máximo común divisor de todos los números escritos, y si este máximo común divisor es igual a [math], el juego ha terminado y perdió el jugador que escribió el último número.

Si Juan comienza el juego (escribe el primer número), ¿cuál de los dos jugadores tiene estrategia ganadora?

ACLARACIÓN: [math] es el producto de todos los números enteros desde [math] hasta [math], es decir, [math].
"Though my eyes could see I still was a blind man"

Avatar de Usuario
Prillo

Colaborador OFO - Jurado
Mensajes: 398
Registrado: Sab 18 Dic, 2010 8:52 pm
Medallas: 2

Re: Problema 5 Selectivo de IMO 2000

Mensaje sin leer por Prillo » Mar 15 Ene, 2013 10:51 pm

Spoiler: mostrar
Probaremos que Pablo tiene estrategia ganadora. Pablo puede asegurarse la victoria como sigue: Si en su primer turno Juan elige el [math] no hay nada que hacer. Sino, si Juan elige un divisor [math] de [math] que no es primo, en el siguiente turno Pablo elige un divisor primo [math] de [math]. Si por el contrario Juan elige un primo [math] entonces en su turno Pablo elige cualquier múltiplo de [math] que divida a [math] (por ejemplo [math]). En cualquier caso un número primo y un múltiplo suyo han sido escrito, por lo cual si Juan y Pablo no quieren perder, en lo que sigue del juego tendrán que elegir números del conjunto [math] que no hayan sido escrito antes. Pero es fácil ver que [math] contiene una cantidad par de elementos, ya que [math] donde [math] es el exponente de [math] en la factorización en primos de [math], y al menos uno de los primos [math] y [math] divide exactamente a [math], de donde [math] y en consecuencia [math], como afirmábamos. Se sigue que el primer jugador que no puede escribir un número nuevo de [math] es Juan, forzándolo a elegir un [math] coprimo con [math] y dándole a Pablo la victoria.

Avatar de Usuario
Emerson Soriano

OFO - Mención OFO - Medalla de Oro OFO - Medalla de Plata OFO - Medalla de Bronce
Mensajes: 795
Registrado: Mié 23 Jul, 2014 10:39 am
Medallas: 4

Re: Problema 5 Selectivo de IMO 2000

Mensaje sin leer por Emerson Soriano » Vie 25 Oct, 2019 8:40 pm

Prillo escribió:
Mar 15 Ene, 2013 10:51 pm
Spoiler: mostrar
Probaremos que Pablo tiene estrategia ganadora. Pablo puede asegurarse la victoria como sigue: Si en su primer turno Juan elige el $1$ no hay nada que hacer. Sino, si Juan elige un divisor $d$ de $100!$ que no es primo, en el siguiente turno Pablo elige un divisor primo $p$ de $d$. Si por el contrario Juan elige un primo $p$ entonces en su turno Pablo elige cualquier múltiplo de $p$ que divida a $100!$ (por ejemplo $2p$). En cualquier caso un número primo y un múltiplo suyo han sido escrito, por lo cual si Juan y Pablo no quieren perder, en lo que sigue del juego tendrán que elegir números del conjunto $Q_p=\{px: px|100!\}$ que no hayan sido escrito antes. Pero es fácil ver que $Q_p$ contiene una cantidad par de elementos, ya que $|Q_p|=\prod_{q \text{ primo}}(\alpha_q+1)$ donde $\alpha_q$ es el exponente de $q$ en la factorización en primos de $\frac{100!}{p}$, y al menos uno de los primos $97$ y $89$ divide exactamente a $\frac{100!}{p}$, de donde $2\in\{\alpha_{97}+1,\alpha_{89}+1\}$ y en consecuencia $2| |Q_p|$, como afirmábamos. Se sigue que el primer jugador que no puede escribir un número nuevo de $Q_p$ es Juan, forzándolo a elegir un $k$ coprimo con $p$ y dándole a Pablo la victoria.
Si Juan elige un compuesto, no necesariamente Pablo gana eligiendo un primo adecuado, ya que si Juan elige como número compuesto al producto de todos los divisores primos de $100!$ (o un múltiplo de este), entonces Pablo no ganaría (en ese instante) aún si elige un primo $p$.

Responder