|
| |
|
|
A316632
|
|
a(n) is the Sprague-Grundy value of the Node-Kayles game on the 3 X n lattice graph.
|
|
3
|
|
|
|
2, 1, 1, 0, 3, 3, 2, 2, 2, 3, 3, 5, 2, 4, 1, 3
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
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.
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,more
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
a(14)-a(16) from Max Fan, May 23 2021
|
|
|
STATUS
|
approved
|
| |
|
|
