(This post looks at an 'easy' version of Nim and how to solve it. My next post looks at the solution to the harder variants.)
My first experience with Nim was the simple version ('easy') where you start with a pile of (say) 15 toothpicks. You are allowed to take away 1, 2 or 3 toothpicks in your turn and then it is the other player's turn. You continue taking turns until someone has to take the last toothpick (and they lose).
This type of game is pretty easy to analyze. You can see that if you leave your opponent 1 toothpick you win. And if you leave them 1+4 = 5 toothpicks you also win (since if there are 5 toothpicks and they take 'x', you just take '4-x' on your turn and that leaves 1...giving you the win). So the winning strategy is to leave your opponent with 1 + (some multiple of 4) in the pile. If the pile starts with 15 and you get to go first, take 2 (leaving 13 = 1 + 4(3)) and you are already in a winning position.
Finally, if you are allowed to take 'k' toothpicks on each turn, then just leave 1 + some multiple of (k+1) toothpicks and you win. (And if the rules are that you need to take the last toothpick yourself to win, then just leave 1 + some multiple of k.)
The next variant I had heard of (call it 'hard') extended this game to 3 piles. The version I played had piles of 3, 5 and 8. During your turn you can take 1, 2, or 3 toothpicks from any one pile. Again, the objective of the game was to leave your opponent with the last toothpick.
I'll leave the analysis of this to be a simple case of the 'hardest' case:
- you have any number of piles
- each pile has some number of toothpicks
- during your turn you can take any number of toothpicks from any one pile
What is the winning strategy?
I'll leave this to my next post...but it's actually a fairly easy(!) solution - if you're good at converting numbers to binary and then adding up columns to see if they are even or odd.
No comments:
Post a Comment