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?
(In reply to
Extended calculations. by Brian Smith)
I think my program has a flaw, in that this nim-variant has the tendency to increase the number of heaps to play from, and the algorithm I used is derived from basic misere-nim. So it doesn't account for everything, resulting in improper calclations.
I'll leave the original post below for posterity.
So I amended my program to calculate the misere values, which are the values Jer is seeking. (Player to take the last square loses).
Running this up to 109 gave this:
1 2 2 0 0 3 3 1 4 2 6 5 5 2 7 5 4 3 3 1 4 7 7 5
5 2 8 4 4 6 3 1 8 7 7 5 5 2 2 4 4 6 3 1 8 2 7 5
5 2 8 8 4 6 3 1 4 2 7 5 5 2 8 4 4 6 3 1 8 7 7 5
5 2 8 4 4 6 3 1 8 2 7 5 5 2 8 4 4 6 3 1 8 2 7 5
5 2 8 4 4 6 3 1 8 2 7 5 5
This is eventually periodic. Assuming I didn't make a mistake while adding support for misere numbers then it seems the only way for player 2 to win is to start the game with a 2x4 or 2x5 grid.
(For some reason going higher than 109 gives me an error)
The modified program:
10 Size=109
20 dim Nim(Size+1):dim Mex(Size+1):dim Mis(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:Mis(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 if (Nim(N-J)>1) or (Nv>1) then Mv=Nv else Mv=1-Nv
250 Mis(Mv)=Mis(Mv)+1
270 next J
300 X=0
310 while Mex(X)>0:X=X+1:wend
320 Nim(N)=X
330 X=0
340 while Mis(X)>0:X=X+1:wend
350 print X;
380 if N@24=0 then print
400 next N
410 print
420 print=print
430 end
Edited on December 5, 2021, 3:33 pm
Edited on December 24, 2021, 8:51 am
re: Extended calculations part 2
