Pedidos parciales

Question

Definido el Divisor Poset para cualquier número entero positivo n de la siguiente manera:

• Elementos: todos los divisores positivos de n
• Relación: decimos que a b si a|b.

Para cualquier número entero positivo n podemos definir un juego de dos jugadores en el poset de los divisores para n de la siguiente manera:

• Tablero: Al principio. dibujar el Diagrama de Hasse para el poset divisor en n .
• Movimientos: En el turno de un jugador determinado, debe seleccionar un elemento que aún esté en el tablero y retirarlo, junto con todos los demás elementos que estén ese elemento bajo nuestra relación poset.

Los jugadores 1 y 2 se alternan los movimientos, empezando por un jugador. El jugador que selecciona n pierde. Si n=96 ¿Qué jugador puede garantizar su victoria?

¿Puede alguien ayudarme? ¿Cómo lo reclamo?

Answer 1

Supongamos que el jugador 1 selecciona 48. Quedan 32 y 96. El jugador 2 selecciona 32 y entonces gana. Es decir, 32,96 es una posición ganadora para el jugador actual.

Supongamos que el jugador 1 selecciona 32. Quedan 96,48,24,12,6,3. El jugador 2 selecciona 48 y entonces gana. Es decir, 3,6,12,24,48,96 es una posición ganadora para el jugador actual.

Supongamos que el jugador 1 selecciona 24. Quedan 16, 32, 48 y 96. El jugador 2 selecciona 16 y entonces gana sin importar lo que haga el jugador 1. 16,32,48,96 es una posición ganadora para el jugador actual.

Supongamos que el jugador 1 selecciona 16. Quedan 3,6,12,24,32,48 y 96. Si el jugador 2 elige 48, pierde, porque le quedan 96,32, que es un tablero ganador para el jugador 1. La selección de 32 deja 3,6,12,24,48,96 que también vimos anteriormente sería un tablero ganador para el jugador 1. El jugador 2 seleccionando 24 será una jugada ganadora para el jugador 2 porque 32,48,96 es un tablero perdedor para el jugador actual. 3,6,12,24,32,48,96 es una posición ganadora para el jugador actual.

Supongamos que el jugador 1 selecciona 12. Quedan 8,16,24,32,48,96. El jugador 2 perdería si selecciona 48 porque el jugador 1 seleccionaría 32. El 32 pierde porque el jugador 1 seleccionaría el 48. Seleccionando 24 quedaría 16,32,48,96 que es un tablero ganador para el jugador 1 como el anterior. Si el jugador 2 selecciona 16 entonces quedan 24,32,48 y 96 y el jugador 1 gana seleccionando 24. 24,32,48,96 es una posición ganadora para el jugador actual. Si el jugador 2 selecciona 8, entonces quedan 16,24,32,48,96 y el jugador 2 gana sin importar qué. 16,24,32,48,96 es un tablero perdedor para el jugador actual y 8,16,24,32,48,96 es un tablero ganador para el jugador actual.

Esto debería dar una idea del procedimiento. A medida que hemos trabajado en el cómputo, hemos mantenido un registro del estado del tablero y si están ganando o perdiendo para el jugador actual. Así que si el tablero es tal que Alice encuentra una jugada que deja el tablero en un estado $P$ que está perdiendo para el jugador actual, entonces es una tabla ganadora para el jugador actual. Hemos guardado el cálculo de quién gana en el estado del tablero $P$ porque ya lo hemos hecho antes.