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 2008-12-16 23:08:52