Problema 5 OMM 2003

Enviado por jose el 30 de Enero de 2009 - 23:11.

Problema 5. Se escriben en tarjetas todas las parejas de enteros $(a,b)$ con $1\leq a\leq b \leq 2003$. Dos personas juegan con las tarjetas como sigue: cada jugador en su turno elige $(a,b)$ (que se retira del juego) y escribe el producto ab en el pizarrón (ambos jugadores usan el mismo pizarrón). Pierde el jugador que ocasione que el máximo común divisor de los números escritos hasta ese momento sea $1$. ¿Quién tiene la estrategia ganadora? (Es decir, ¿cuál de los dos jugadores puede inventar un método que asegure su tirunfo?)

Solución

Por:

jose

Fecha:

18 Jul 2010

Solución:

La estrategia es así: El primer jugador debe tomar la tarjeta $(1,p)$ de tal manera que la cantidad de tarjetas que tenga un múltiplo de $p$ en alguno de los dos lugares sea impar. Esto se debe a que cuando se acaban las tarjetas con múltiplos de $p$, si se elige cualquier otra, el mcd deja de ser $p$ y se vuelve $1$. Para $3$ funciona: Hay $667$ múltiplos de $3$ entre $1$ y $2003$, entonces hay $2003-667=1336$ números que no son múltiplos de $3$. Vamos a calcular la cantidad de tarjetas que no tienen múltiplos de $3$ en ninguno de los dos lugares, y el total de tarjetas que se pueden obtener. El total es $C(2003,2)=2003(1001)$. El total de tarjetas que no tienen múltiplos de $3$ es $(1336,2)=668(1335)$. Restando ambas cantidades nos da el total de tarjetas que tienen al menos un mútliplo de $3$ en alguno de los dos lugares que es $2005003-891780=1113223$ que es impar. Por lo tanto el jugador que elige la tarjeta $(1,3)$ va a ganar.