XIII OIM - 1998 - Solucion al problema 1 Opciones

[jaschnei]

Hola, años más tarde me encuentro con este foro y quiero plantearles la solucion al problema 1, por favor déjenme saber si les parece correcta

PROBLEMA 1:
Dados 98 puntos en una circunferencia, María y José se turnan para dibujar segmentos, con extremos en esos puntos. Trazan un segmento por turno, sin repetir los segmentos ya trazados. El juego termina cuando todos los puntos se han usado como extremo de algún segmento, y gana la persona que dibuja el último segmento. José inicia el juego. ¿Quién puede asegurar la victoria?


Solución:

Es claro que una jugada ganadora ocurre si quedan 1 ó 2 puntos sin que hayan sido usados como extremo de algún segmento: (i)

i.1: Si queda un solo punto sin ser usado como extremo de un segmento, existen 97 jugadas ganadoras, una hacia cada uno de los otros 97 puntos.
i.2: Si quedan dos puntos, basta con unir estos dos puntos con un segmento entre ellos para tener la jugada ganadora.

Por otro lado también es claro que con tres puntos sin ser usados, no es posible ganar en una sola jugada, debido a que en cada jugada solo podemos usar como máximo dos puntos que no hayan sido usado como extremo de un segmento. (ii)

De (i) y (ii) se concluye que la cantidad máxima de puntos sin usar es 2, para ganar terminar (ganar) el juego en esa jugada (iii).

De (iii) se puede concluir que el perdedor es aquel que al jugar, se vea forzado a dejar uno ó dos puntos sin usar luego de su jugada y por lo tanto el oponente gana debido a (i). Esta situación la llamaremos "A"

"A" se fuerza cuando existen 95 puntos utilizados y estos 95 puntos tienen todos los posibles segmentos entre sí ya trazados.

En "A" como hay 95 puntos usados, existen 3 puntos sin usar y debido a (ii) no es posible ganar es dicha jugada. Las aternativas son:

Trazar un segmento entre alguno de los puntos libres hacia alguno de los 95 que ya tienen segmentos, dejando 2 puntos sin usar y por lo tanto su oponente gana en la siguiente jugada (i.2)
Trazar un segmento entre dos de los puntos sin usar, dejando 1 punto sin usar y por lo tanto su oponente gana en la siguiente jugada (i.1)

Para forzar A deben existir 95.94/2 = 4465 segmentos que son el total de todos los posibles segmentos entre 95 puntos. Como 4465 es impar, implica que José fue el último en jugar porque José es quien comienza el juego y por lo tanto después de sus jugadas siempre habrá un número impar de segmentos al alternarse con María.

En este sentido, José puede forzar la situación "A" cuando al solamente quedar 3 puntos sin usar, no los utiliza en su jugada sino que traza uno de los 4465 segmentos entre los 95 puntos que ya fueron usados al menos una vez. Si María sigue la misma táctica de no usar ninguno de los 3 puntos libres, en la jugada 4466 se verá en la situación "A" por lo que será la perdedora. Si antes de la jugada 4466, quedando solamente 3 puntos sin usar, María usa alguno de ellos, José gana haciendo las jugadas descritas en (i.1) o (i.2)

En conclusión, José puede asegurarse la victoria.

Mensaje modificado por jaschnei el Oct 12 2016, 10:55 PM