Nim fractals (Q2877906)

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)].