Problema 5 Selectivo de IMO 2000

[Nacho]

Juan y Pablo juegan, por turnos, al siguiente juego: cada uno, en su turno, escribe un número natural que sea divisor positivo de $100!$ 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 $1$, 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: $100!$ es el producto de todos los números enteros desde $1$ hasta $100$, es decir, $100!=1\cdot 2\cdot 3\cdots 97\cdot 98\cdot 99\cdot 100$.

[Prillo]

Spoiler: mostrar

Probaremos que Pablo tiene estrategia ganadora. Pablo puede asegurarse la victoria como sigue: Si en su primer turno Juan elige el [math]1 no hay nada que hacer. Sino, si Juan elige un divisor [math]d de [math]100! que no es primo, en el siguiente turno Pablo elige un divisor primo [math]p de [math]d. Si por el contrario Juan elige un primo [math]p entonces en su turno Pablo elige cualquier múltiplo de [math]p que divida a [math]100! (por ejemplo [math]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 [math]Q_p=\{px: px|100!\} que no hayan sido escrito antes. Pero es fácil ver que [math]Q_p contiene una cantidad par de elementos, ya que [math]|Q_p|=\prod_{q \text{ primo}}(\alpha_q+1) donde [math]\alpha_q es el exponente de [math]q en la factorización en primos de [math]\frac{100!}{p}, y al menos uno de los primos [math]97 y [math]89 divide exactamente a [math]\frac{100!}{p}, de donde [math]2\in\{\alpha_{97}+1,\alpha_{89}+1\} y en consecuencia [math]2| |Q_p|, como afirmábamos. Se sigue que el primer jugador que no puede escribir un número nuevo de [math]Q_p es Juan, forzándolo a elegir un [math]k coprimo con [math]p y dándole a Pablo la victoria.

[Emerson Soriano]

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$.