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?

  • 1
    $\begingroup$ You found out the answer but you lack any proof or even intuition behind the answer? In what sense then can you claim to have 'found' the answer? So, here's what you should do: write down in what sense you say you have 'found' the answer ... that should translate into an intuition, and then hopefully you can try and prove it .. $\endgroup$ – Bram28 Mar 1 '18 at 20:42
  • $\begingroup$ @Bram28 The answer is "whoever starts the game always wins" and value of N doesn't matter. $\endgroup$ – Zephyr Mar 1 '18 at 20:43
  • $\begingroup$ OK, good ... so how did you 'find' that? What convinces you that the few examples you did generalize to any $N$? Try to express that, and you should have an intuition right there ... and on your way towards a proof (assuming the intuition is correct of course!) $\endgroup$ – Bram28 Mar 1 '18 at 20:44
  • $\begingroup$ @Bram28 Actually I tried for 8-10 examples and found this to be true always. I am not able to generalize it and that's why I posted it here looking for some convincing proof. $\endgroup$ – Zephyr Mar 1 '18 at 20:46
  • $\begingroup$ Hmm, but if you have no sense of how it generalizes, then again I question your claim that you have 'found out the answer' ... at best you might 'start to suspect the answer is ...' ... But anyway, I don't want to nit-pick semantics here ... let's see how we can find an intuition: are you not finding any kind of pattern in these examples at all? Maybe first try and systematically write out those 8-10 cases .. And maybe post that analysis: we always enjoy seeing some effort, and it might help us see a pattern you're not seeing. $\endgroup$ – Bram28 Mar 1 '18 at 20:49

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.

  • $\begingroup$ Why are you assuming that first player will always pick 1 at the start ? Can you extend the proof if player 1 picks any other piece ? $\endgroup$ – Zephyr Mar 2 '18 at 6:07
  • 1
    $\begingroup$ More specifically, for $N=1$ it's clear the first player $P$ always wins. So for $N\ge2$, assume the second player $Q$ has a winning strategy, i.e. whatever sequence of moves $P$ makes, $Q$ has a sequence of moves that wins the game. We abuse this fact. How does $P$ "swap places" with $Q$? You have to note that $1$ is a divisor of every $n\in\mathbb{N}$. $\endgroup$ – palmpo Mar 2 '18 at 14:28
  • 2
    $\begingroup$ @Zephyr: the point is that picking $1$ is essentially passing your turn. If the second player picks $12$ we are missing $1,2,3,4,6,12$. If the first player picks $12$ instead, the second player is where the first would be. The existence of a pass move lets the first player win. Either the pass move wins or it doesn't. If it doesn't, the first player makes the winning response to the pass move and wins. This is called strategy stealing. $\endgroup$ – Ross Millikan Mar 2 '18 at 15:00

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.