login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 11 06:08 EDT 2022. Contains 356046 sequences. (Running on oeis4.)