You and your friend decide to play the following game: You start with two piles of stones. The first with $n_1$ stones and the second with $n_2$ stones. You take turns, with your friend starting first. At each turn, a player can choose one of the two piles of stones, and pick any positive number of stones from this pile, and then you do the same. The person who picks the last stone wins. Suppose your friend start the game with an equal number of stones in each pile, show that you have a winning strategy.

Can anyone please help me with this problem .I am able to prove it with $n=1,2$ or $3$ where $n$ is the number of stones picked.But i m confused that how to proceed with a generalized proof

  • 2
    $\begingroup$ Keep 'em equal! $\endgroup$ – Lord Shark the Unknown Aug 17 '17 at 16:36
  • $\begingroup$ When you say $n$, do you mean the number of piles? Or the number of stones in each pile? $\endgroup$ – Sergio Enrique Yarza Acuña Aug 17 '17 at 16:36
  • 3
    $\begingroup$ You can copy what the opponent is doing but apply it to the other pile, until one pile is empty and you pick the rest. $\endgroup$ – dromastyx Aug 17 '17 at 16:36
  • $\begingroup$ A slightly more interesting variant would be if the person who picks the last stone loses. $\endgroup$ – Jens Aug 17 '17 at 17:11
  • $\begingroup$ @Ross Millikan, Yes you are right, I have edited that! $\endgroup$ – Jungle Boy Aug 17 '17 at 17:35

It is only sufficeint to take the same number of stones as your friend chooses; but take it from the opposite pile.

In other words at each turn:

  • if your friend take $x$ stones from the first pile, you should take $x$ stones from the second pile.

  • if your friend take $x$ stones from the second pile, you should take $x$ stones from the first pile.

This is awinning strategy.


In any game like this the positions divide into N positions, which are wins for the Next player and P positions, which are wins for the Previous player. An N position can always move to a P position and that is a good move. A P position can only move to N positions. As long as the player receiving N positions plays properly, he will win. The task is to find the P positions.

Here the hints claim that having the two piles equal is a P position and all others are N positions, so the first player wins if $n1 \neq n2$ and loses if $n1 = n2$. You should be able to see that from any P position you can reach an N position and that from N positions you can only reach P positions as claimed.

As asked, starting with two equal piles of stones the game is a second player win. You just mirror your opponent's moves, keeping the piles equal, and you will win. Eventually your opponent will take the last stone in one pile and you will take the last one in the other.


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.