3
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ It seems like this can be solved with a simple strategy stealing argument. $\endgroup$ – Euler....IS_ALIVE Oct 2 '15 at 3:40
  • 1
    $\begingroup$ Consider two cases. Case I: Starting off by picking $1$ is a winning move for the first player. Case II: Starting off by picking $1$ is a losing move for the first player. Case I is easy. Now, what about Case II? $\endgroup$ – bof Oct 2 '15 at 3:48
  • $\begingroup$ @Euler....IS_ALIVE, could you please elaborate? $\endgroup$ – user230560 Oct 2 '15 at 4:02
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Could you please elaborate on "Apply every single rule of R" in point 1? Based on this this, you say that A can win. How? $\endgroup$ – user230560 Oct 2 '15 at 5:00
  • $\begingroup$ What that part means is that, suppose $R$ is $B$ 's winning strategy and $R$ has no element of $y=1$. Then $R'$ = {For state $S$, if $B$ removes $x$, then $A$ removes $y$ (with same set of $S,x,y$ in R)} U {Remove 1 in $A$ 's first move} is a winning strategy for $A$. $\endgroup$ – cr001 Oct 2 '15 at 5:06
  • $\begingroup$ Okay, so I do get what is R'. But how will it lead to a winning strategy for A? $\endgroup$ – user230560 Oct 2 '15 at 5:10
  • $\begingroup$ $R'$ is a winning strategy for $A$ because we assume that $R$ is a winning strategy for $B$, and $R'$ and $R$ are basically the same with player order switched and the extra first removal of $1$. $\endgroup$ – cr001 Oct 2 '15 at 5:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy