Multiplicative modular Nim (MuM)

This paper introduces Multiplicative Modular Nim (MuM), an impartial variant of classical Nim where heap interaction is governed by modular multiplication rather than the traditional bitwise XOR (nim-sum). The author begins by formulating the game over prime moduli \(p\), replacing traditional subtraction rules with heap-size reduction constraints modulo \(p\) and introducing an automatic heap consolidation mechanism. Under this framework, a Bouton-style winning strategy is established, demonstrating that losing positions (\(P\)-positions) correspond precisely to states whose total product is congruent to \(1 \pmod p\). To formalize this algebraically, the author constructs an analogue to the Sprague-Grundy theorem by introducing a game-theoretic value termed the \textit{mumber}. Evaluated via a multiplicative \(\operatorname{mex}_p\) recursion over the unit domain \((\mathbb{Z}/p\mathbb{Z})^\times\), the mumber of any position is shown to equal the heap product modulo \(p\), establishing that game composition is governed by modular multiplication. The analysis is then generalized to composite moduli \(m\), where heaps are restricted to unit classes modulo \(m\) (i.e., \(\gcd(h_i, m) = 1\)). Using the Chinese remainder theorem (CRT), the author demonstrates how composite MuM games decompose into independent subgames corresponding to their prime-power factors. To illustrate the transition between multi-heap play and the single-heap regime, consider the position \((3, 3, 5) \pmod 4\). Because \(5 \ge 4\), the game remains in the threshold region with three active heaps. The initial product is \(3 \times 3 \times 5 = 45 \equiv 1 \pmod 4\), marking it as an initial \(P\)-position. If a player moves on heap \(3\) to reduce it to \(1\), the resulting position \((1, 3, 5)\) maintains a heap \(\ge 4\), keeping multi-heap play active with \(P \equiv 3 \pmod 4\). Conversely, if a player reduces heap \(5\) to \(3\), the remaining heaps become \((3, 3, 3)\). Because all heaps are now strictly smaller than \(m=4\), the automatic consolidation rule immediately merges them between turns into a single heap \(H = 3 \times 3 \times 3 = 27\) (\(27 \equiv 3 \pmod 4\)), seamlessly shifting the game into a single-heap subtraction game isomorphic to \(\text{SUB}(3)\). Finally, the paper extends the framework to finite fields \(\mathbb{F}(p^n)\), motivated by pedagogical and cryptographic applications such as the AES S-box. By interpreting integer heaps as polynomials modulo an irreducible polynomial \(I(x)\), the author formulates \textit{polynomial MuM}, resolving the many-to-one mapping between integers and field elements via a ``synonym-move exclusion rule. Overall, the paper provides a thorough, self-contained, and original contribution to combinatorial game theory, successfully embedding multiplicative arithmetic and finite field structures into a playable, impartial game framework.

Cites work

This page was built for publication: Multiplicative modular Nim (MuM)

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