A316632 a(n) is the Sprague-Grundy value of the Node-Kayles game on the 3 X n lattice graph.

2, 1, 1, 0, 3, 3, 2, 2, 2, 3, 3, 5, 2, 4, 1, 3

Offset: 1

Author

Sierra Brown, Spencer Daugherty, Eugene Fiorini, Barbara Maldonado, Sean E. Rainville, Riley S. Waechter, Wing Hong Tony Wong, Jul 13 2018

Keywords

• nonn
• more

Comments

The Node-Kayles game on the 1 X n lattice graph (i.e., path) is equivalent to the Dawson's chess game and thus produces the same Sprague-Grundy values as A002187.

The Node-Kayles game on the 2 X n lattice graph (i.e., ladder graph) produces the Sprague-Grundy values 1,0,1,0,1,0,..., which are periodic with period 2 (A000035).

The Node-Kayles game on the 4 X n lattice graph produces the Sprague-Grundy values 0,0,0,0,0,..., which are constantly 0 (A000004).

Examples

			a(1) is the Sprague-Grundy value of the Node-Kayles game played on the 3 X 1 lattice graph, which is a path of length 3. Hence, a(1)=2, which is the third term in the sequence A002187.
a(2) is the Sprague-Grundy value of the Node-Kayles game played on the 3 X 2 lattice graph, which is a ladder with three rungs. The first player has two possible moves: to color the a corner vertex, which has degree 2, or to color a vertex with degree 3. If the player colors a vertex of degree 2, the resultant graph is a path of length 3. As mentioned before, the Sprague-Grundy value of the Node-Kayles game played on a path of length 3 is 2. If the player colors a vertex of degree 3, the resultant graph consists of two isolated vertices. The Sprague-Grundy value of the Node-Kayles game played on two isolated vertices is 0. Hence, a(2) = mex{0,2} = 1, where mex is the minimum excluded function.
		

References

• E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Volume 1, A K Peters, 2001.

Links

• Sierra Brown, Spencer Daugherty, Eugene Fiorini, Barbara Maldonado, Diego Manzano-Ruiz, Sean Rainville, Riley Waechter, and Tony W. H. Wong, Nimber Sequences of Node-Kayles Games, J. Int. Seq., Vol. 23 (2020), Article 20.3.5.
• Max Fan, Generalized Node-Kayles calculator implemented in Rust
• Riley S. Waechter, Python program

Crossrefs

Cf. A000004, A000035, A002187.

Programs

Haskell

pickCoords n = sequence [[0,1,2], [0..n-1]]
mex list = head (filter (`notElem` list) [0..(maximum list+1)])
checkAdj [x,y] [n,m] = not ((x==n && abs(y-m) <= 1) || (y==m && abs (x-n) <= 1))
nextMoves max history = filter (\move -> null history || all (checkAdj move) history) (pickCoords max)
calcNimber max history | null (nextMoves max history) = 0 | otherwise = mex (map (\move -> calcNimber max (history ++ [move])) (nextMoves max history))
a316632 n = calcNimber n [] -- Max Fan, May 23 2021

Rust

// See Fan link. - Max Fan, May 23 2021

Extensions

a(14)-a(16) from Max Fan, May 23 2021