A game of
nim is played with one pile of 30 tokens. The two player takes turns taking tokens off the pile. Whoever takes the last token wins.
To make the game a little more interesting, the rules have been changes slightly:
A player may take 1, 3, 4, or 5 tokens but not 2.
What is the best starting move and what is the general strategy?
The 2nd player loses if it's his turn, and there are 8K or 8K+2 tokens left. In those cases, whatever he does, the first player can always take some tokens (proof left as an exercise!) and reach another losing position for the 2nd player, until the case for K=0 will be reached.
So, the winning move is start by taking 4 tokens, leaving 26 on the table.
Analysis
