Results 1 to 7 of 7

Math Help - Game Theory

  1. #1
    Banned
    Joined
    Sep 2008
    Posts
    47

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jan 2009
    Posts
    3
    I think player 2. Notice that 2009 is divisible by 7. No matter what player 1 takes he loses. 3+4=7.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Sep 2008
    Posts
    47
    Can you please elaborate on your proof? I don't quite understand your logic. Thanks!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Sep 2008
    Posts
    47
    Does anyone have any other ideas on this question?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by Winding Function View Post
    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...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Sep 2008
    Posts
    47
    Quote Originally Posted by awkward View Post
    ... 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!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by Winding Function View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Game theory: Are there any other equilibria in this game?
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: March 7th 2012, 06:45 PM
  2. Game Theory: Hotelling game with 3 players
    Posted in the Advanced Applied Math Forum
    Replies: 2
    Last Post: March 26th 2011, 02:08 AM
  3. Game Theory: 2xn game
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: November 17th 2010, 03:53 PM
  4. [game theory] Election game
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: April 22nd 2009, 07:32 AM
  5. Game theory
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: January 18th 2009, 09:09 AM

Search Tags


/mathhelpforum @mathhelpforum