Journal of Integer Sequences, Vol. 17 (2014), Article 14.7.8

Nim Fractals


Tanya Khovanova
Department of Mathematics
MIT
Cambridge, MA 02139
USA

Joshua Xiong
Acton-Boxborough Regional High School
Acton, MA 01719
USA

Abstract:

We enumerate P-positions in the game of Nim in two different ways. In one series of sequences we enumerate them by the maximum number of counters in a pile. In another series of sequences we enumerate them by the total number of counters.

We show that the game of Nim can be viewed as a cellular automaton, where the total number of counters divided by 2 can be considered as a generation in which P-positions are born. We prove that the three-pile Nim sequence enumerated by the total number of counters is a famous toothpick sequence based on the Ulam-Warburton cellular automaton. We introduce 10 new sequences.


Full version:  pdf,    dvi,    ps,    latex    


(Concerned with sequences A000007 A000012 A000027 A016945 A048883 A130665 A236305 A237686 A237711 A238147 A238759 A241522 A241523 A241717 A241718 A241731.)


Received May 22 2014; revised version received July 13 2014. Published in Journal of Integer Sequences, July 14 2014.


Return to Journal of Integer Sequences home page