Two players start with a pile of stones.
1st player takes any number of stones from the pile, but not all of them.
Then the players alternate, taking up to twice as many stones
as their opponent just took.
The player taking the last stone (or stones) is the winner.

Question: If you and your friend start with 100 stones, what is the smallest amount of stones you should take on your 1st turn, and how will you proceed to win the game?

I don't think I have a concise way to explain this yet, but I believe the solution is 3.  I arrived at this by working backwards.  It was a little tedious and I won't go through every step but I'll illustrate the process.

No matter what your opponent did on his prior turn, you can always take 1 or 2 stones on your next turn. 

So if you start a turn with only 1 or 2 stones remaining, you always win by taking the remaining stones.

If you start a turn with 3 stones remaining, you will lose if you take just 1 or 2 stones, as your opponent will then take the rest.  Thus you can only win by taking all 3.  So if you start a turn with 3 stones remaining, you can only win if your opponent took 2+ stones on his last turn.

This creates a "safe spot" where you can land your opponent - if you start with 4 stones, and take just 1, you will have forced a win.  So you always win if you start a turn with 4 stones. 

If you start a turn with 5 stones, you can only win by taking all 5.  This is only possible if your opponent took 3+ on their prior turn.  Thus 5 is also a "safe spot" - you can put your opponent there by starting on 6 and taking 1, or starting on 7 and taking 2.

Continue working backwards like this, and you eventually find that 97 is a "safe spot" where you can leave your opponent without a forced win.  So the least number of stones you can take to start the game is 3.

In fact, I believe that the only other possible starting move is to take 11 stones, leaving your opponent with 89.  This is the only other "safe spot" you can reach from the beginning of the game.  If you take anything other than 3 or 11 stones to start, your opponent can use the same strategy to force a win for themselves.

Edited on June 30, 2014, 3:21 pm

Posted by tomarken on 2014-06-30 12:45:24