Two players play a game and the rules are as follows:
$N$ wooden pieces (marked with numbers from $1$ to $N$) are placed in a bottle. A player takes out some piece, say "$x$", from the bottle, and then also takes out "all pieces numbered by divisors of $x$". Play continues in alternating fashion until one piece (last piece) remains in the bottle. The player who picks the last piece wins the game.
If both players play optimally, then, for a given $N$ and given player who starts the game, who wins the game ?
I worked out eight-to-ten examples and believe the answer to be
Whoever starts the game always wins, regardless of $N$.
I am interested in the proof or intuition of the answer.
Can someone please help?
There is a simple existence proof of a first player win, but it doesn't help us find the winning strategy. As there are no draws and it is a finite game, one player must have a winning strategy for each $N$. For a given $N$, assume the second player can win. The second player must have a winning answer to the first player taking $1$. Whatever that move is, the first player can make it and be in the same place as the second player would be responding to $1$, so the first player can win. We have reached a contradiction, so the assumption that the second player can win must be wrong.
A similar proof works for many symmetric impartial games.