Econ Papers Daily / 期刊论文
乘法模尼姆游戏 (MuM)
Multiplicative Modular Nim (MuM)
摘要
We introduce Multiplicative Modular Nim (MuM), a variant of Nim in which the traditional nim-sum is replaced by heap-size multiplication modulo m. We establish a complete theory for this game, beginning with a direct, Bouton-style analysis for prime moduli. Our central result is an analogue of the Sprague-Grundy theorem, where we define a game-theoretic value, the mumber, for each position via a multiplicative mex recursion. We prove that these mumbers are equivalent to the heap-product modulo m, and show that multiplicative composition of MuM positions is governed by modular multiplication, in contrast to classical Nim where composition is governed by XOR (nim-sum). For composite moduli, we show that MuM decomposes via the Chinese Remainder Theorem into independent subgames corresponding to its prime-power factors. We extend the game to finite fields \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {F}(p^n)$$\end{document}, motivated by the pedagogical need to make the algebra of the AES S-box more accessible. We demonstrate that a sound game in this domain requires an integer heap model with synonym-move exclusion to resolve the many-to-one mapping from integer heaps to field elements. To our knowledge, this is the first systematic analysis of a multiplicative modular variant of Nim and its extension into a complete, non-additive combinatorial game algebra.
中文摘要
我们引入乘法模尼姆游戏（MuM），这是尼姆游戏的一个变体，其中传统的尼姆和被堆大小模m的乘法所取代。我们为该游戏建立了完整的理论，首先对素数模数进行了直接的、类似布顿风格的分析。我们的核心结果是斯普拉格-格伦迪定理的类比，其中我们通过乘法mex递归为每个局面定义了一个博弈论值——mumber。我们证明这些mumber等价于堆乘积模m，并表明MuM局面的乘法组合由模乘法支配，这与经典尼姆中由异或（尼姆和）支配的组合形成对比。对于合数模数，我们证明MuM可通过中国剩余定理分解为对应于其素数幂因子的独立子游戏。受使AES S盒的代数更易于理解的教学需求驱动，我们将该游戏扩展到有限域\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {F}(p^n)$$\end{document}。我们证明，在该域中构建合理的游戏需要采用整数堆模型并排除同义词移动，以解决从整数堆到域元素的多对一映射问题。据我们所知，这是首次对尼姆的乘法模变体及其扩展为完整非加性组合博弈代数进行的系统分析。