Partitioning set $[n] = \{1, \dots, n\}$ into subsets of size at most $m$ such that all sums are powers of $m$

想象一下，你是一位大师级建筑师，任务是使用恰好 $n$ 块独特的砖块（编号为 1 到 $n$）来建造一座城市。你的目标不仅仅是堆叠它们；你必须将它们分组为不同的街区（称为“部分”），且必须遵守两条严格的规则。首先，任何街区都不能过于拥挤，最多只能容纳 $m$ 块砖。其次，任何街区内砖块的总“重量”必须是一个特定魔数 $m$ 的完美幂次（例如 $m^0=1, m^1=m, m^2$ 等）。这个谜题属于组合数学的世界，这是研究如何排列、计数和分组数字的一个数学分支。这就像是在解决一个巨大的、无限的数独游戏，其规则随着网格大小的变化而改变。数学家之所以关注它，是因为理解数字如何分解并重新组合，揭示了数学结构的深层奥秘，就像理解原子如何结合有助于我们制造新材料一样。

你即将阅读的论文探讨了一个特定且棘手的版本。作者弗拉基米尔·古尔维奇（Vladimir Gurvich）和玛丽亚·瑙莫娃（Mariya Naumova）将魔数 $m$ 设定为 3。这意味着他们试图将 1 到 $n$ 的数字分成大小为 1、2 或 3 的组，且每组的和都是 3 的幂（1, 3, 9, 27 等）。他们已经知道，对于 $m=2$，对于任何 $n$ 都有且仅有一种方法可以实现。他们也知道，对于大于 3 的 $m$，对于无穷多个 $n$ 值，该问题是无法实现的。但对于 $m=3$，答案仍然是一个谜。作者们强烈怀疑（猜想）对于每一个 $n$，都存在一个解。

为了测试这一点，他们并没有仅仅靠猜测；他们建立了一个数学上的安全网。他们证明了，如果某个 $n$ 不存在解，那么那个“坏”数字必须具有非常特定的、奇特的形状。它必须看起来像 $n = 3t + 3k + 2$，并且必须避开其他某些特定的模式。这就像一位侦探说：“如果发生了犯罪，嫌疑人必须戴着红帽子、跛行且是左撇子。”如果你发现一个不符合该描述的嫌疑人，你就知道他们不是罪犯。作者利用这种逻辑排除了大量的数字。他们还通过计算机模拟检查了直到 844 的每一个数字，在所有这些案例中都找到了解。他们甚至探索了一个稍微宽松的版本，即允许一个数字被使用两次的“拟划分”（quasi-partition），并证明了在该版本中也存在解。虽然他们还没有证明该谜题对每个 $n$ 都可解，但他们已经将寻找反例的范围缩小到了一个非常小、非常具体的数字列表。他们相信，对于几乎所有的其他数字，解不仅是可能的，而且通常是唯一的。

数字分组大游戏

想象你有一个装有编号瓷砖的袋子，编号从 1 到某个很大的数字 $n$。你的任务是将这些瓷砖分类成堆。但这里有规则！

1. 规模规则： 每堆最多可以有 3 块瓷砖。
2. 求和规则： 每堆中的数字之和必须是“3 的幂”。这意味着总和必须是 1, 3, 9, 27, 81 等等。

这就是“3-好划分”问题。作者提出了一个简单但顽固的问题：无论我们开始有多少块瓷砖，我们是否总能做到这一点？

长期以来，数学家都知道“2-好”划分（即每堆最多 2 块且和为 2 的幂）的答案。事实证明，对于任何 $n$，都有且仅有一种方法可以实现。但对于 3，规则变得复杂了。作者怀疑答案是“是的，它总是可能的”，但他们需要证明这一点。

“关键”嫌疑人

与其试图证明它对“每一个”数字都有效（这很难），作者决定寻找那些“坏蛋”——即失效的数字。他们推论，如果存在一个无法进行分组的数字 $n$，那么它一定是一个“关键”数字。

他们证明了，如果这样一个关键数字存在，它不能是随机的数字。它必须戴着一个非常特定的伪装。它必须是形式为：
$$n = 3t + 3k + 2$$
并且必须满足关于 $k$ 相对于 $t$ 的大小的一些额外条件。

这就像一名俱乐部的保安。保安说：“如果你想不带票潜入，你必须戴着绿帽子并提着蓝色的包。”如果你看到一个人戴着红帽子，你就知道他肯定不是那个偷偷溜进来的入侵者。作者证明了任何不符合这个“绿帽子”描述的数字都是安全的；我们知道如何对这些数字进行分组。这排除了大量的可能性。

计算机检查

即便有了这些精妙的数学推导，仍然有一些符合“绿帽子”描述的数字。为了确保万无一失，作者（在计算机程序员德米特里·雷宾（Dmitry Rybin）的帮助下）编写了一个程序，检查了直到 844 的每一个数字。

• 结果： 对于从 1 到 844 的每一个数字，他们都找到了一种完美分组的方法。
• 结论： 计算机没有发现任何一个“坏”数字。这有力地支持了他们的猜想，即该谜题对所有人都是可解的。

“拟划分”的转折

作者还尝试了一个略微不同的游戏。如果允许一个数字被使用 两次 会怎样？他们称之为“拟划分”。想象你有一块多余的数字 3 的瓷砖，所以你可以把它用在两个不同的堆中。
他们证明了，对于一个特定的数字范围，你总是可以解决这个版本的谜题，且数字 3（具体说是 $3^t$）就是那个被使用两次的数字。这成为了理解更难问题的有用阶梯。

有多少种方法？

论文中最有趣的部分之一是计算分组的不同方式。

• 对于某些数字（如 1, 2, 3, 4 以及许多其他数字），有恰好一种方法。这就像一把锁对应一把钥匙。
• 对于数字 13，以及像 $3t - 3$ 这样的数字，有恰好两种方法。
• 对于几乎所有其他数字，他们怀疑有超过两种方法。

他们甚至发现了一个特殊的规则（命题 2），即如果你知道解中哪些三个数字的组合（三元组）在其中，你就可以推导出整个谜题。这就像是在说：“如果你知道房间里哪三个好朋友在一起，你就了解了整个社交动态。”

总结

作者尚未解决宇宙中每一个数字的谜题。仍然有一些棘手的数字（如 35, 38, 89 和 101）尚未被他们的数学完全排除。然而，他们已经表明，如果解不存在，它必须是这些非常特定、罕见的数字之一。

他们确信“3-好划分”对于每个数字 $n$ 都是存在的。他们排除了容易失败的情况，用计算机检查了前 844 个数字，并发现谜题始终有解。谜题不在于是否能对数字进行分组，而在于对于那些非常大的数字，我们有多少种分组的方法。证明它对每一个数字都有效的旅程仍在继续，但现在的路径已变得清晰得多。