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,1

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).

References

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

Links

Table of n, a(n) for n=1..16.

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

Example

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.

Prog

(Rust) // See Fan link. - Max Fan, May 23 2021
(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

Crossrefs

Cf. A000004, A000035, A002187.

Sequence in context: A321914 A321746 A133830 * A111571 A051509 A124816

Adjacent sequences: A316629 A316630 A316631 * A316633 A316634 A316635

Keyword

nonn,more

Author

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

Extensions

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

Status

approved