Two players start with a 2xN grid of squares. Each player, in turn, may take either a single square or a 2x2 block of squares. The player who takes the last square loses.
For what values of N does player 2 win?
So I finally got around to writing a small Ubasic program to calculate the values for the normal game (who takes the last square wins).
Going out to 2x120 values, starting with 2x1:
0 2 2 1 4 3 3 1 4 2 6 5 0 2 7 1 4 3 3 1 4 7 7 5
0 2 8 4 4 6 3 1 8 7 7 5 0 2 2 1 4 6 3 1 8 2 7 5
0 2 8 1 4 6 3 1 4 2 7 5 0 2 8 1 4 6 3 1 8 7 7 5
0 2 8 1 4 6 3 1 8 2 7 5 0 2 8 1 4 6 3 1 8 2 7 5
0 2 8 1 4 6 3 1 8 2 7 5 0 2 8 1 4 6 3 1 8 2 7 5
So the values eventually become periodic, showing player 1 can win a game of regular 2xn grid nim so long as N mod 12 is not equal to 1.
The program:
10 Size=120
20 dim Nim(Size+1):dim Mex(Size+1)
30 Nim(0)=0
40 print=print+"output.txt"
100 for N=1 to Size
110 for I=0 to N:Mex(I)=0:next I
200 for J=1 to N
210 if J<=ceil(N/2) then Nv=bitxor(1,bitxor(Nim(J-1),Nim(N-J)))
220 :else Nv=bitxor(Nim(J-2),Nim(N-J))
230 Mex(Nv)=Mex(Nv)+1
240 next J
300 X=0
310 while Mex(X)>0:X=X+1:wend
320 Nim(N)=X:print X;
330 if N@24=0 then print
400 next N
410 print
420 print=print
430 end
Extended calculations.
