A game of 11 marbles wherein each player can either pick one or two marbles from the total. Starting from Player A & then Player B alternatively. This continues till all the marbles are picked. The winner is the one having odd number of marbles.
What is the strategy to be followed for Player A & B to win?. What happens for higher total number of marbles (13, 15 etc )?
"Move" means your turn, "Push" means your opponents turn. We can build a robust solution by starting on the ground level and working our way up.
You win if you:
Move at 1, even; Push to 1, odd
Move at 2
These are obvious.
Now, we can see that if you win by Push to n, odd, then you win by Move at n+1, even, and Move at n+2 odd (since either allows you to Push to n). Additionally, if you win by Move at n, even, and Move at n+1, even, then you also win by Push to n+2, even.
So, assume you win at
Move at n, even; Push to n, odd
Move at n+1
By the rules above:
Push to n, odd > Move at n+2, odd
Move at n, even + Move at n+1, even > Push to n+2, even
Push to n+2, even > Move at n+3, odd
Move at n+1, odd + Move at n+2, odd > Push to n+3, odd
Push to n+2, even > Move at n+4, even
Move at n+2, odd + Move at n+3, odd > Push to n+4, odd
Push to n+3, odd > Move at n+5, odd
Push to n+4, odd > Move at n+5, even
To summarize results, we have
Move at n+2, odd; Push to n+2, even
Move at n+3, odd; Push to n+3, odd
Move at n+4, even; Push to n+4, odd
Move at n+5
Which gives us the conditions
Move at (n+4), even; Push to (n+4), odd
Move at (n+4) + 1
... and allows us to start again.
Thus, the game is precisely equivalent if you subtract a multiple of four from the number of marbles.

Posted by AvalonXQ
on 20081216 23:08:52 