🔢 mathematics

The Nim-Sum of a Random Integer Partition

本文确定了整数 $N$ 的划分中丢失位置比例的一阶渐近行为。该比例在 $1/(\sqrt{N}\log N)$ 的尺度上趋于零，但在按其自然尺度归一化后并不收敛；相反，它在二进边界附近表现出一种由泊松奇偶性转换驱动的二进锯齿状模式。

原作者： Daewon Kim

发布于 2026-08-28✓ Author reviewed ⓘ

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Daewon Kim

原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一个以石堆为基础的游戏，两名玩家轮流从单个堆中取走任意数量的石子。目标是成为最后一个移动的人，或者反过来，迫使对手陷入无法进行有效移动的境地。这是尼姆游戏（Nim），一个经典的策略谜题，已被研究了一个多世纪。获胜的秘诀不在于计算石子的总数，而在于使用一种以二进制方式混合加法和减法的规则，将各堆的大小进行特定的组合。如果这种组合结果为零，那么轮到移动的玩家注定会输，假设其对手发挥完美。几十年来，数学家们已经知道如何为任何特定的堆排列识别出这些必败位置。但一个更深层、更难以捉摸的问题仍然存在：如果你仅仅收集固定数量的石子，并将它们随机分成若干堆，这种随机排列恰好成为一个必败位置的概率会有多大？

这个问题处于博弈论与整数拆分（即研究一个数如何分解为若干个更小的正整数的数学领域）的交汇点。虽然单个游戏的规则是精确且确定性的，但当起始位置是随机选择时，这些游戏的行为却出人意地复杂。一个自然的问题是，随着石子总数的增加，必败位置出现的频率是否会趋于一个简单的渐近模式。然而，夏威夷大学马诺阿分校大卫·金（Daewon Kim）的新工作揭示了答案远比简单的趋于稳定要复杂得多。随着石子总数的增加，必败位置出现的原始概率实际上会趋向于零，这意味着它们变得越来越稀有。但如果我们将这个概率按照其自然的基准进行缩放，得到一个归一化后的密度值，这个密度值并不会平滑地趋向于一个稳定的平均值，而是以一种锯齿状的、重复的模式进行振荡，且无论总石子数变得多么大，这种模式永远不会真正稳定下来。

金的研究重点关注总石子数为偶数的情况，因为游戏的规则使得奇数总数永远不可能构成必败位置。通过使用精确的计数方法，该研究计算了总数高达两万的所有可能排列中必败位置的准确数量，而不是通过随机抽样。研究结果表明，这个归一化后的密度并不趋向于一个单一的常数值。相反，它在剧烈波动，呈现出一种每当问题的自然规模跨越 2 的幂次方时就会重复一次的锯齿状模式。如果你将归一化后的概率对石堆大小进行绘图，你会看到一条线在低点和高点之间稳步攀升，然后急剧跌落，接着又开始攀升。这个循环无限重复，这意味着归一化后的密度值会填满 1 到 2 倍特定缩放因子之间的整个区间。

驱动这种行为的机制根植于游戏获胜规则的二进制特性。当一个大数被分解成较小的部分时，最小的部分就像一个随机源，扰乱了二进制数的低位，使它们看起来均匀且不可预测。最大的部分非常罕见，因此很少影响结果。然而，存在一个特定的中间范围的部件大小，它充当了一个关键的瓶颈。在这个范围内，部件既足够大以产生显著影响，又不至于大到消失。落在这一特定范围内的部件数量决定了结果。由于这个范围随着总石子数的增长而移动，游戏的平衡也会随之倾斜。当问题的自然规模略低于 2 的幂次方时，平衡向一方倾斜；当跨越该阈值时，平衡发生翻转，导致概率跳变。

为了理解这一点，可以将这个过程比作一个时钟，每当达到某个特定小时时就会重置，但时钟指针移动的速度会随着时钟本身的大小而改变。随着总石子数的增加，“关键范围”的部件大小向上移动。归一化后的必败位置概率的振荡，其关键驱动因素在于该范围内部件数量的奇偶性。由于部件的分布受类似于泊松分布（一种常用于描述稀有事件的统计模型）的规律支配，处于该关键范围内的部件为偶数个数还是奇数个数会发生变化，这种奇偶性的波动创造了锯齿状模式。研究证实，随着总石子数的增加，归一化后的密度并不会收敛于一个单一的数字，而是会在特定区间内持续振荡。

这项研究不仅限于必败位置。它还表明，对于每一个固定的目标尼姆和（nim-sum），其密度具有相同的阶衰减，并且在经过相同的归一化后，遵循相同的二进锯齿状轮廓。这表明，游戏的二进制结构在随机分布的堆中留下了永久的印记，这种印记拒绝被涉及的巨大数字所平滑化。

为了验证这些理论预测，作者对总数高达两万的所有可能的排列进行了精确计算。这需要一种复杂的计算方法，将其视为一个大规模计数练习，并使用专门的算法来处理数十亿种可能的组合。计算结果与理论预测高度吻合，证实了锯齿状模式是真实的，而非数学模型的产物。数据表明，归一化概率的上升和下降过程完全符合理论预测，且在问题的自然规模跨越 2 的幂次方时发生精确的剧烈转变。

研究还探讨了这些峰值与谷值之间转换的性质。虽然图形看起来具有尖锐的、不连续的跳跃，但有限规模分析表明，这些跳跃实际上是在一个极小的尺度上被平滑化的。这种平滑化受描述随机事件奇偶性的相同统计规律支配。随着总石子数的增加，这种平滑发生的窗口变得越来越窄，使得看似突发的跳跃实际上是在一个不断缩小的范围内，由关键范围内部件数量的奇偶性所驱动的逐渐转变。

最终，这项工作完整地描述了当起始配置是随机选择时，尼姆游戏中必败位置的分布情况。它解决了关于这些位置出现频率的长期疑问，表明它们并不遵循简单的、稳定的趋势。相反，它们受部件大小与游戏二进制结构之间复杂的相互作用支配。研究结果强调了一个更广泛的数学原理：即使在看似随机和平滑的系统中，深层的算术结构也能创造出持久且尖锐的模式，这些模式能够抵抗平均化。游戏的二进制特性确保了特定的信息块始终可见且具有影响力，无论系统规模多么庞大，都会创造出一种随着数字增大而永远重复的节奏。

技术摘要：随机整数拆分的 Nim 和

问题陈述
本文研究了具有固定总数 $N$ 的普通 Nim 位置的计数性质。在 Nim 游戏中，一个位置由一组堆的大小（多重集）定义。根据 Bouton 定理，当且仅当堆的大小的按位异或（XOR）为零时，该位置是一个必败位置。当忽略堆的顺序时，这些位置对应于 $N$ 的整数拆分。

核心问题是确定比率 $a_N / p(N)$ 的渐近行为，其中 $p(N)$ 是 $N$ 的整数拆分总数，而 $a_N$ 是异或和为零的拆分数量。由于奇偶性限制是显而易见的（对于奇数 $N$ ， $a_N = 0$ ，因为总和与异或和具有相同的最低有效位），因此研究重点在于偶数 $N$ 时必败位置的分布。对于偶数 $N$ ，原始密度趋于零，而经过适当归一化后的密度表现出一种复杂的、非收敛的振荡行为，传统的拆分渐近理论无法捕捉这种行为。

方法论
作者采用了一种结合组合分解、概率建模和解析数论的多维度方法：

组合分解： 作者根据拆分中各部分的重数将拆分 $\lambda$ 分解为两个部分。如果部分 $j$ 出现了 $c_j$ 次，则将其写为 $c_j = 2r_j + \varepsilon_j$ ，其中 $\varepsilon_j \in \{0, 1\}$ 。偶数个副本（ $2r_j$ ）在异或和中相互抵消，从而只留下“奇数核心”（ $\varepsilon_j=1$ 的部分）。这使得问题转化为分析由互不相同的项组成的拆分的异或和。
玻尔兹曼采样（Boltzmann Sampling）： 为了利用独立性，研究转向了总规模为随机变量的玻尔兹曼模型。在该模型中，包含互不相同部分的指示变量是独立的伯努利变量。通过将整数划分为相对于临界尺度 $J$ $J$ 的三个二进区间来分析零异或和的概率：
- 低值块（ $[1, J)$ ）： 这些较小的部分会使低位二进制位随机化，从而产生接近均匀分布的低位比特。
- 临界块（ $[J, 2J)$ ）： 该范围决定了一阶概率。该范围内的每个整数都具有相同的最高 $J$ 位比特；该块异或和的最高有效位为零，当且仅当该范围内被选部分的数量为偶数，且在此条件下，低值块必须匹配剩余的低位比特残差。
- 高值块（ $[2J, \infty)$ ）： 这些较大的部分较为稀少，对一阶项的贡献可以忽略不计。
二进层级与 Walsh 分析： 作者利用 Walsh 分析（ $\mathbb{F}_2$ 上的特征正交性）推导精确的有限公式并进行精细化近似。通过保留更多的上位二进制位，构建了一个公式层级，使得二进层级可以将玻尔兹曼近似精细化到任意代数阶，而向固定规模拆分的转移仅在第一阶建立。
鞍点分析： 为了将结果从玻尔兹曼模型（随机规模）转移回固定规模的拆分，论文对生成函数使用了鞍点法。由于必败位置的生成函数具有偶函数性质，作者识别出了两个相等的鞍点（分别靠近 $q = e^{-t_N}$ 和 $q = -e^{-t_N}$ ）。
精确计算： 实现了一种基于 Walsh 公式和中国剩余定理（CRT）的精确算法，用于计算高达 $N=20,000$ 的 $a_N$ 。这用于验证渐近公式并分析有限规模的修正项。

主要结果
本文确立了必败位置密度的阶一渐近行为。令 $\tau_N = \pi/\sqrt{6N}$ 且 $B_N = \log(1/\tau_N)/\tau_N$ 。令 $J_N$ 为在乘法距离上最接近 $B_N$ 的 2 的幂，并定义 $\Lambda_N = e^{-\tau_N J_N}/\tau_N$ 。

对于偶数 $N$ ，比率由下式给出：
$\frac{a_N}{p(N)} = \frac{1 + e^{-2\Lambda_N} + o(1)}{J_N}$

关键发现包括：

非收敛性： 归一化密度 $B_N \frac{a_N}{p(N)}$ 并不收敛。相反，其子序列极限集是整个区间 $[1, 2]$ 。
二进锯齿波： 其行为遵循“二进锯齿”模式。随着 $N$ 的增加，每当 $B_N$ 跨越 2 的幂次时，数值在每个二进制阶段从 1 上升到 2，并在跨越新的 2 的幂次时跌回 1。
泊松平滑： 在二进边界处的表观不连续性通过泊松随机变量的奇偶律在缩小的尺度上得到平滑。具体而言，如果 $N$ 趋向于一个边界，使得 $\tau_N K - \log(1/\tau_N) \to c$ （其中 $K$ 是 2 的幂），则极限为 $1 + e^{-2e^{-c}}$ 。
一般 Nim 和： 该结果并非仅限于零异或和。对于任何固定的目标 Nim 和 $x$ ，具有 Nim 和 $x$ 的拆分的密度在奇偶类 $N \equiv x \pmod 2$ 上遵循相同的阶一轮廓。
精确计数： 论文将 OEIS 序列 A048833 扩展到了索引 10,000（总规模 $N=20,000$ ），提供的精确数据证实了预测的尺度以及有限规模误差的结构。

意义与主张
本文声称提供了不受限整数拆分中必败 Nim 位置的完整阶一渐近描述。其意义在于揭示了即使存在一个临界二进块（在低位被随机化后，高位变得微不足道），一个“平滑”的随机结构（整数拆分）仍会保留一个尖锐的算术特征（二进制奇偶性）。

这项工作证明了必败位置的密度数量级为 $\Theta(1/(\sqrt{N} \log N))$ ，但缺乏单一的渐近常数。作者强调，“二进层级”允许进行任意代数阶的精细化，这解释了为什么即使在一阶定理有效时，有限规模修正项仍然显著。论文得出结论，非收敛性是该问题的结构性特征，而非近似失效；此外，阶段之间的转换受泊松变量奇偶性的支配。

本文并未声称解决了目标 Nim 和增长或受限拆分的更一般问题，并指出这些是自然的开放性问题。同时，作者也并未声称其有限规模修正分析构成了一个完整的二阶定理，因为该分析依赖于形式展开而非对高阶导数的一致界限。

类似论文