Defined the Divisor Poset for any positive integer n as follows:
- Elements: all of the positive divisors of n
- Relation: we say that a ⪯ b if a|b.
For any positive integer n, we can define a two-player game on the divisor poset for n as follows:
- Board: At the start. draw the Hasse diagram for the divisor poset on n.
- Moves: On a given player's turn, they must select an element still on the board and remove it, along with all other elemts that are ⪯ that element under our poset relation.
Players 1 and 2 alternate moves, with 1 player starting. The player who selects n loses. If n=96, which player can guarantee that they win?
Can someone help me? How to I claim it?
Suppose player 1 selects 48. 32 and 96 are left. Player 2 selects 32 and then wins. That is 32,96 is a winning position for the current player.
Suppose player 1 selects 32. 96,48,24,12,6,3 are left. Player 2 selects 48 and then wins. That is 3,6,12,24,48,96 is a winning position for current player.
Suppose player 1 selects 24. 16,32,48 and 96 are left. Player 2 selects 16 and then wins no matter what player 1 does. 16,32,48,96 is a winning position for current player.
Suppose player 1 selects 16. 3,6,12,24,32,48 and 96 are left. Player 2 selecting 48 is a losing move because it will leave 96,32 which is a winning board for player 1. Selecting 32 leaves 3,6,12,24,48,96 which we also saw above would be a winning board for player 1. Player 2 selecting 24 will be a winning move for player 2 because 32,48,96 is a losing board for the current player. 3,6,12,24,32,48,96 is a winning position for current player.
Suppose player 1 selects 12. 8,16,24,32,48,96 are left. Player 2 would lose if selecting 48 because player 1 would select 32. 32 is losing because player 1 would select 48. Selecting 24 would leave 16,32,48,96 which is a winning board for player 1 as above. If player 2 selects 16 then 24,32,48 and 96 are left and player 1 wins by selecting 24. 24,32,48,96 is a winning position for current player. If player 2 selects 8 then 16,24,32,48,96 are left and player 2 wins no matter what. 16,24,32,48,96 is a losing board for current player and 8,16,24,32,48,96 is a winning board for current player.
This should give the idea of the procedure. As we have worked through the computation, we have kept track of board status and whether or not they are winning or losing for the current player. So if the board is such that Alice finds a move that leaves the board in a state $P$ that is losing for the current player, then that is a winning board for current player. We have saved the computation of who wins on board state $P$ because we have already done it before.