I was solving this SPOJ question, which is as below:
N wooden pieces (marked with numbers 1 to N) are placed in a transparent bottle. On his turn the first player takes out some piece (numbered x) and all the pieces numbered by divisors of x that are present in the transparent bottle. The second player picks another number and removes it and its divisors as well. Play continues in an alternating fashion until all pieces have been removed from the bottle. The player who removes the last piece from the bottle wins the game.
Both players play optimally. Given N (the number of wooden pieces in the transparent bottle initially) and the name of the player who starts the game, determine the winner.
Google search says that the one who starts the game always wins. Although this can be proven by solving some test cases, how do I prove this mathematically?
Based on what Euler and bof says, I think the idea is basically that removing 1 is same as an "empty move" that can be performed at most once.
For the sake of contradiction, suppose the second player $B$ has a winning strategy. Suppose the first player is $A$. Suppose $B$ 's winning strategy is the set of rules R = {For state $S$, if $A$ removes $x$, then $B$ removes $y$}. State variable $S$ is basically a subset of {$1,2,...,N$} indicating the remaining numbers.
(1) If $R$ does not contain any element with $y=1$, then $A$ removes $1$ in his first move and apply every single rule of $R$ (obviously with $A$ and $B$ switched in the rules). Obviously $A$ can win and contradicts it's $B$ 's winning strategy.
(2) If $R$ contains an element with $y=1$, then it is a contradiction itself because $1$ is already removed in $A$ 's first move (as $1$ is a divisor of any number) and that rule of $R$ is not even valid thus $R$ cannot be a winning strategy.
So $B$ cannot have a winning strategy and it must be either a tie or $A$ winning. Since tie is not possible $A$ must be winning.
Some additional notes: I know this is not a constructive proof that explicitly gives a winning strategy for $A$ and thus not very intuitive. I think the logic in my last sentence is valid but if not please give me a comment. The prerequisite for my logic is that if $A$ and $B$ are playing optimal moves and tie is not possible, then either $A$ or $B$ must have a winning strategy.