Interesting Esoterica

Nim Fractals

Article by Khovanova, Tanya and Xiong, Joshua
  • Published in 2014
  • Added on
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.

Links

Other information

key
Khovanova2014
type
article
date_added
2014-06-05
date_published
2014-05-01
pages
19

BibTeX entry

@article{Khovanova2014,
	key = {Khovanova2014},
	type = {article},
	title = {Nim Fractals},
	author = {Khovanova, Tanya and Xiong, Joshua},
	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.},
	comment = {},
	date_added = {2014-06-05},
	date_published = {2014-05-01},
	urls = {http://arxiv.org/abs/1405.5942,http://arxiv.org/pdf/1405.5942v1},
	collections = {Games to play with friends,Combinatorics},
	month = {may},
	pages = 19,
	url = {http://arxiv.org/abs/1405.5942 http://arxiv.org/pdf/1405.5942v1},
	year = 2014,
	archivePrefix = {arXiv},
	eprint = {1405.5942},
	primaryClass = {math.CO},
	urldate = {2014-06-05}
}