Nim fractals

MaRDI QIDQ2877906zbMATH OpenFDO

Authors Tanya Khovanova, Joshua Xiong

Publication date 28 August 2014

Published in Journal of Integer Sequences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.5942, http://www.emis.de/journals/JIS/VOL17/Khovanova/khova6.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

cellular automatoncombinatorial gamesNimP-position

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80) Combinatorial games (91A46)

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.

Review text

The authors study two particular families of sequences associated with the widely known combinatorial take-away game of Nim. Let \(k\) be the (fixed) number of piles of token. Note that some pile can be empty. Let \(a_k(n)\) (resp., \(d_k(n)\)) be the number of P-positions such that each pile has no more than \(n\) token (resp., the largest pile has \(n\) token). Let \(A_k(n)\) (resp., \(D_k(n)\)) be the number of P-positions such that the total number of token is no more than (resp., is equal to) \(2n\).NEWLINENEWLINEA major part of the paper is about combinatorial properties of these sequences. The authors give formulas to compute these sequences for two, three or more piles. Many arguments rely on Nim-sum and base-\(2\) expansions of integers. In the last sections, connections with cellular automata are revealed.NEWLINENEWLINEAbout the Ulam-Warburton cellular automaton discussed in this paper, the paper [\textit{A. Fink} et al., Int. J. Game Theory 43, No. 2, 269--281 (2014; Zbl 1294.91039)] could be of interest. For connections with (one-dimensional) cellular automata, also see the paper [\textit{U. Larsson}, J. Comb. Theory, Ser. A 120, No. 5, 1116--1130 (2013; Zbl 1288.91029)].

Recommendations

• Fractal sequences and restricted Nim.
• Three-pile Sharing Nim and the quadratic time winning strategy
• Square, rectangular and triangular Nim games
• Nim-induced dynamical systems over \(\mathbb Z_2\)
• Nimlike games with generalized bases

Cited in

(9)

• The game of n-times nim
• P-positions in modular extensions to Nim
• A family of Nim-like arrays: the locator theorem
• LIM is not slim
• Fractal sequences and restricted Nim.
• scientific article; zbMATH DE number 2214423 (Why is no real title available?)
• The Sierpiński sieve of Nim-varieties and binomial coefficients
• Nim-induced dynamical systems over \(\mathbb Z_2\)
• Periodicity and other structure in a colorful family of Nim-like arrays

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Nim fractals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2877906)