Thread: Game Theory

A game begins with 2009 marbles. The players take turns taking the marbles. On each turn, a player can take 3, 4, or 7 stones, except that if only 1 or 2 stones remain, the player may remove them all. The player that takes the last stone wins the game. Which player has the winning strategy, the first or second player? Why?

I think player 2. Notice that 2009 is divisible by 7. No matter what player 1 takes he loses. 3+4=7.

Can you please elaborate on your proof? I don't quite understand your logic. Thanks!

Does anyone have any other ideas on this question?

Originally Posted by Winding Function

A game begins with 2009 marbles. The players take turns taking the marbles. On each turn, a player can take 3, 4, or 7 stones, except that if only 1 or 2 stones remain, the player may remove them all. The player that takes the last stone wins the game. Which player has the winning strategy, the first or second player? Why?

Hi Winding Function,

Here is a suggestion. Write down the numbers 1,2,...,30 (30 is somewhat arbitrary) and proceed to mark each number as a win or a loss for the player whose move it is when facing that number of marbles. You can immediately mark 1, 2, 3, 4, and 7 as winners. Work from low numbers to high and mark a number n as a loss if n-3, n-4, and n-7 are all marked as winners; otherwise mark n as a win. You can see, for example, that 5 and 6 are losers.

I think that by the time you reach n=30 you will see a pattern emerging in the losing numbers. Then make a guess as to the pattern and see if you can prove your guess correct. If 30 numbers aren't enough to see a pattern you can extend your search to larger numbers.

Hope this helps...

Originally Posted by awkward

... and mark a number n as a loss if n-3, n-4, and n-7 are all marked as winners; otherwise mark n as a win.

Why does that work?

I've found a pattern, WWWWLLWWWWL keeps repeating. But how does this help me?

Thanks!

Originally Posted by Winding Function

Why does that work?

I've found a pattern, WWWWLLWWWWL keeps repeating. But how does this help me?

Thanks!

Hi Winding Function,

The "Why it works" is as follows: Suppose there are n marbles in the pile. If it's your move you want to leave your opponent with a lost position. You can do that be removing 3, 4, or 7 marbles; if removing 3 marbles, for example, will leave your opponent with a loss, then that's what you will choose to do, so the original position is a win for you. But if all of your choices-- n-3, n-4, and n-7-- all lead to a winning position for your opponent, then you are in a losing position.

You have found the pattern, which is an important step, but I think to make more progress you will need to write down the numbers associated with the wins and losses. It looks from your reply like the pattern has length 11. If so, you should be able to write a statement like "I think the losing positions are of the form 11m + x, where x = ___, ___, or ___." (You fill in the blanks, with values in the range 0 to 10.) Then you can try to prove your guess. One possibility is a proof by induction over m, but there are other ways that should work too.