Results 1 to 4 of 4

Math Help - n x m game

  1. #1
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    1

    n x m game

    Suppose 2 people are playing a game. They have two strings of nucleotides, one of length n and the other of length m. At every turn, a person must delete 2 nucleotides from 1 string (either the 1st or the 2nd) and 1 nucleotide from the other. The person who cannot move loses the game. Who wins the game? What's the winning strategy for each n and m?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    1
    Is there an easy, efficient formula to try and solve this, or is it a brute force problem? I mean, I could try for like, 10 for m and n, but what about any value?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2006
    Posts
    401
    Neglecting the nucleotides, since that is practically useless information, we basically have the following game. A position in the game is an ordered pair of non-negative integers; the initial position is (n, m).
    From the position (j, k), a player can move to (j-2, k-1), provided that j-2 and k-1 are non-negative; similarly, a playe rcan move to (j-1, k-2), provided that j-1 and k-2 are non-negative, too. These are the only legal moves. The player who has no legal move loses. We can classify a position, B, as Bad if it's a guaranteed loss for the player who must move from it (assuming the opponent doesn't make a mistake), and position G, as Good if there is at least one winning move from it.

    In particular, we can see a pattern rather quickly.

    0 1 2 3 4 5 6 7 8 9 10
    -------------------------
    0 | B B B B B B B B B B B
    1 | B B G G G G G G G G G
    2 | B G G G G G G G G G G
    3 | B G G B B B B B B B B
    4 | B G G B B G G G G G G
    5 | B G G B G G G G G G G
    6 | B G G B G G B B B B B
    7 | B G G B G G B B G G G
    8 | B G G B G G B G G G G
    9 | B G G B G G B G G B B
    10| B G G B G G B G G B B

    That is, we have:

    (0, 0): B

    (1, 0), (0, 1): B

    (2, 0), (1, 1), (0, 2): B

    (3, 0), (0, 3): B
    (2, 1), (1, 2): G

    (4, 0), (0, 4): B
    (3, 1), (2, 2), (1, 3): G

    (5, 0), (0, 5): B
    (4, 1), (3, 2), (2, 3), (1, 4): G

    (6, 0), (3, 3), (0, 6): B
    (5, 1), (4, 2), (2, 4), (1, 5): G

    (7, 0), (4, 3), (3, 4), (0, 7): B
    (6, 1), (5, 2), (2, 5), (1, 6): G

    (8, 0), (5, 3), (4, 4), (3, 5), (0, 8): B
    (7, 1), (6, 2), (2, 6), (1, 7): G

    (9, 0), (6, 3), (3, 6), (0, 9): B
    (8, 1), (7, 2), (5, 4), (4, 5), (2, 7), (1, 8): G

    And so forth.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Apr 2006
    Posts
    399
    Awards
    1
    Quote Originally Posted by AfterShock View Post
    Neglecting the nucleotides, since that is practically useless information, we basically have the following game. A position in the game is an ordered pair of non-negative integers; the initial position is (n, m).
    From the position (j, k), a player can move to (j-2, k-1), provided that j-2 and k-1 are non-negative; similarly, a playe rcan move to (j-1, k-2), provided that j-1 and k-2 are non-negative, too. These are the only legal moves. The player who has no legal move loses. We can classify a position, B, as Bad if it's a guaranteed loss for the player who must move from it (assuming the opponent doesn't make a mistake), and position G, as Good if there is at least one winning move from it.

    In particular, we can see a pattern rather quickly.

    0 1 2 3 4 5 6 7 8 9 10
    -------------------------
    0 | B B B B B B B B B B B
    1 | B B G G G G G G G G G
    2 | B G G G G G G G G G G
    3 | B G G B B B B B B B B
    4 | B G G B B G G G G G G
    5 | B G G B G G G G G G G
    6 | B G G B G G B B B B B
    7 | B G G B G G B B G G G
    8 | B G G B G G B G G G G
    9 | B G G B G G B G G B B
    10| B G G B G G B G G B B

    That is, we have:

    (0, 0): B

    (1, 0), (0, 1): B

    (2, 0), (1, 1), (0, 2): B

    (3, 0), (0, 3): B
    (2, 1), (1, 2): G

    (4, 0), (0, 4): B
    (3, 1), (2, 2), (1, 3): G

    (5, 0), (0, 5): B
    (4, 1), (3, 2), (2, 3), (1, 4): G

    (6, 0), (3, 3), (0, 6): B
    (5, 1), (4, 2), (2, 4), (1, 5): G

    (7, 0), (4, 3), (3, 4), (0, 7): B
    (6, 1), (5, 2), (2, 5), (1, 6): G

    (8, 0), (5, 3), (4, 4), (3, 5), (0, 8): B
    (7, 1), (6, 2), (2, 6), (1, 7): G

    (9, 0), (6, 3), (3, 6), (0, 9): B
    (8, 1), (7, 2), (5, 4), (4, 5), (2, 7), (1, 8): G

    And so forth.
    I analyzed the game as far as you did but I could not find the pattern. Putting the results into a matrix reveals it. Nice work!
    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, 07:45 PM
  2. Game Theory: Hotelling game with 3 players
    Posted in the Advanced Applied Math Forum
    Replies: 2
    Last Post: March 26th 2011, 03:08 AM
  3. Game Theory: 2xn game
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: November 17th 2010, 04:53 PM
  4. [game theory] Election game
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: April 22nd 2009, 08:32 AM
  5. Sequential-form game (game tree diagram)
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: October 5th 2008, 07:51 PM

Search Tags


/mathhelpforum @mathhelpforum