# n x m game

• Oct 9th 2006, 12:44 PM
fifthrapiers
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?
• Oct 10th 2006, 12:43 PM
fifthrapiers
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?
• Oct 13th 2006, 02:40 AM
AfterShock
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.
• Oct 13th 2006, 04:37 PM
JakeD
Quote:

Originally Posted by AfterShock
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!