Background info
This game is a misere version of a nim-type game. Misere nim is played very similarly to regular nim, the only real change in strategy is when there is exactly one heap with at least 2 chips; the winning move there is to create an odd number of singleton heaps. So in order to determine what the winning positions are in the 2xN game, it is necessary to determine both regular and misere nim values for its game states.
If the nim value of any game state is known then it is trivial to tell if it is a winning state, 0 is a win state and anything else is a losing state.
If the nim values for all the possible results of a rectangle are known then the nim value of the whole rectangle can be found by listing all those values and finding the minimum excluded value, that value is the nim value of the rectangle.
If a game state has multiple pieces whose nim values are known then the whole state has a nim value equal to the nim-sum (bitwise xor) of all the individual pieces.
Analysis
Legal moves in the 2xN nim game have a tendency to fracture the game field into a larger number of smaller pieces.
Taking a large square from a 2xR rectangle can leave a 2x(R-1) rectangle or a pair of 2xS and 2xT rectangles with S+T=R-2. In the case of a 2x2 rectangle the move takes the entire rectanlge leaving the empty state.
Taking a small square can be done by either removing a singleton square from the board or taking a small square from a 2xR rectangle leaving a small square plus either a 2x(R-1) rectangle or a pair of 2xS and 2xT rectangles with S+T=R-1.
As an example, the 2x4 rectangle has four distinct moves: Take a 2x2 at the end leaving a 2x2, take a 2x2 in the middle leaving a pair of 2x1, take a 1x1 at the end leaving a singleton and a 2x3, or taking a 1x1 in the middle leaving a singleton, a 2x1, and a 2x2. In general a 2xR rectangle will have R legal moves, ceil(R/2) moves taking a small square and floor(R/2) moves taking a large square.
Nim Calculation
Now to calculate nim values for the regular play version of the game. The trivial cases: An empty board has a nim value of 0 and the 1x1 square has a nim value of 1. Then the larger rectanlges can be built up iteratively:
2x1 moves | nim values | nim sum
{1} | {1} | 1
2x1 nim value = 0
2x2 moves | nim values | nim sum
{2x1, 1} | {0, 1} | 1
{empty} | {0} | 0
2x2 nim value = 2
2x3 moves | nim values | nim sum
{2x2, 1} | {2, 1} | 3
{2x1, 1, 2x1} | {0, 1, 0} | 1
{2x1} | {0} | 0
2x3 nim value = 2
2x4 moves | nim values | nim sum
{2x3, 1} | {2, 1} | 3
{2x2, 1, 2x1} | {2, 1, 0} | 3
{2x2} | {2} | 2
{2x1, 2x1} | {0, 0} | 0
2x4 nim value = 1
2x5 moves | nim values | nim sum
{2x4, 1} | {1, 1} | 0
{2x3, 1, 2x1} | {2, 1, 0} | 3
{2x2, 1, 2x2} | {2, 1, 2} | 1
{2x3} | {2} | 2
{2x2, 2x1} | {2, 0} | 1
2x5 nim value = 4
2x6 moves | nim values | nim sum
{2x5, 1} | {4, 1} | 5
{2x4, 1, 2x1} | {1, 1, 0} | 0
{2x3, 1, 2x2} | {2, 1, 2} | 1
{2x4} | {1} | 0
{2x3, 2x1} | {2, 0} | 2
{2x2, 2x2} | {2, 2} | 0
2x6 nim value = 3
Misere Calculaiton
Misere calculations are almost identical to regular calculations excpet when there are no nim values of at least 2, then the misere sum is inverted. These values will ultimately be the values needed for the game as described in the problem.
2x1 moves | nim values | misere sum
{1} | {1} | 0
2x1 misere value = 1
2x2 moves | nim values | misere sum
{2x1, 1} | {0, 1} | 0
{empty} | {0} | 1
2x2 misere value = 2
2x3 moves | nim values | misere sum
{2x2, 1} | {2, 1} | 3
{2x1, 1, 2x1} | {0, 1, 0} | 0
{2x1} | {0} | 1
2x3 misere value = 2
2x4 moves | nim values | misere sum
{2x3, 1} | {2, 1} | 3
{2x2, 1, 2x1} | {2, 1, 0} | 3
{2x2} | {2} | 2
{2x1, 2x1} | {0, 0} | 1
2x4 misere value = 0
2x5 moves | nim values | misere sum
{2x4, 1} | {1, 1} | 1
{2x3, 1, 2x1} | {2, 1, 0} | 3
{2x2, 1, 2x2} | {2, 1, 2} | 1
{2x3} | {2} | 2
{2x2, 2x1} | {2, 0} | 1
2x5 misere value = 0
2x6 moves | nim values | misere sum
{2x5, 1} | {4, 1} | 5
{2x4, 1, 2x1} | {1, 1, 0} | 1
{2x3, 1, 2x2} | {2, 1, 2} | 1
{2x4} | {1} | 1
{2x3, 2x1} | {2, 0} | 2
{2x2, 2x2} | {2, 2} | 0
2x6 misere value = 3
From the misere values calculated of the rectangles 2xN for N=1 to 6 only the 2x4 and 2x5 rectangles are losing starts for the first player.
Solution
