Reply to comment
You're in a glitzy casino in Las Vegas. Having tried your hand at everything from Roulette to Black Jack, you've managed to lose most of your money and have only one dollar left.
What's worse, with all the champagne and everything, you've misbehaved and the management has made it very clear that you're not allowed any more games. But you need two dollars to get the bus back to the hotel.
Two shady-looking characters at the bar offer you a game: they have a pile of 15 stones. Each of you in turn is to take your choice of 1, 2, 3, 4 or 5 stones from the pile. The person who takes the last stone gets one dollar from the person who drew previously, and the third person neither wins nor loses.
You're to draw first. You're sure that both of the other players will play to their best personal advantage and won't make any mistakes. Should you agree to play the game?
The solutionThe answer is yes, you should agree to play, as you can make sure that you win. Let's assume that the three players are Alice, Bob and Cindy, and that they play in the alphabetical order of their names. The key is to look at the game in reverse: first consider what happens if 1 stone is left and Alice draws first, then what happens if 2 stones are left and Alice draws first, etc, all the way up to 15.
Obviously, if there are either 1,2,3,4 or 5 stones left, then Alice can win simply by taking all the stones. Cindy will lose and Bob will neither win nor lose.
If there are 6 stones left then Alice will most definitely lose: no matter how many stones she takes, there will be 5 or less stones left, which Bob will take in one go and inflict defeat on Alice.
If there are 7 stones left and Alice takes one, then Bob is faced with six and will most definitely lose, as we have just seen. The victor will be Cindy, and Alice will neither win nor lose. Alice should not, however, take more than one stone, as this would give victory to Bob and defeat to Alice.
And here is where things start repeating: if there are 8,9,10,11 or 12 stones left, then by taking 1, 2, 3, 4 or 5 stones, Alice can present Bob with seven stones. As we have just seen, Bob cannot win, but only avoid defeat by taking 1 stone. This inflicts defeat on Cindy and gives victory to Alice. The situations with 8, 9, 10, 11 or 12 stones left are exactly the same as those with 1, 2, 3, 4 or 5 stones left.
Not surprisingly, then, when there are 13 stones left, Alice will lose whatever she does, as in the 6 stone situation: no matter how many stones she takes, there will be between 8 and 12 left, guaranteeing Bob a sure win and Alice a sure loss.
14 is like 7: if Alice takes 1 stone, Bob cannot help but lose, Cindy wins and Alice neither wins nor loses.
And finally here we are at 15, where the cycle of seven starts all over again. By taking 1 stone, Alice presents 14 stones to Bob. To prevent a loss he must take 1 stone. This means that Cindy is faced by 13 stones and will most definitely lose - which means that Alice wins!
In fact, we see that if you draw first, you should only refuse to play the game when there are 6 or 13 stones left, as in all other cases you are guaranteed a win or a neutral result. As things repeat in a cycle of 7, you can immediately work out if you should play, no matter how many stones you are presented with. Only if the number of stones is of the form 6+7k, where k is a positive whole number, will you lose.
This table shows the outcome of the game in each situation, assuming that Alice draws first and each player makes the best-possible move from their point of view. A 1 means a win, a -1 a loss and a 0 neither. In the right column we see the number of stones Alice should take to obtain the result.
This game was first investigated by the mathematician and chess champion Emanuel Lasker (1868-1941) in a 1931 book on games.
Back to main puzzle page