All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Games
Leonardo's game (Posted on 2014-06-27) Difficulty: 3 of 5
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?

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Possible solution | Comment 1 of 3

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

Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2020 by Animus Pactum Consulting. All rights reserved. Privacy Information