这道组合难题怎么解? 第1页

Willard的回答完全解决了更一般的问题。其方法比较"exterior" (在operators的世界里观察、用的是存在性证明)并用到 之类比较“大”的对象。

但是对一个弱结论我们可以初等证明：（称 这样的有理数2-幂分数）

任一个 开始的操作序列（可数长），其各分量的并集无法遍历任何非退化区间里的2-幂分数。

证明：事实上我们证明

对这个序列各分量取并集，其聚点有限。

固定一个操作序列 ，其中总排好顺序 ， 。我们知道 单调，而 时中间项行为不明。但考虑序列：

那么

引理： 每个分量关于t单调不增。
证明：设某次操作 对 取平均（再排序），不妨设
( )。则

对每个：检查即可。

（事实上，对任何向量 , 对t单调减。）

所以每个分量 是个单减非负数列（关于 ）故收敛。从而

也收敛。

不难证明个收敛数列并集的聚点只能是各自的极限，故有限。特别地，这个并集不能遍历区间上的2-幂分数。

这个方法好在简单。但如果一起考虑所有序列似乎就不行了，但可以问： 到底能收敛到哪（当序列变化）？ 只有 （如果假设序列中没有平凡步）。

Willard知友的答案我完全看不懂。我自己想了这道题，然后把它想出来了。

我们不妨设，禁止拿两个电荷量相同的小球碰撞。考察关于这些小球的操作。

引理1：从任意电荷量分配出发，对任意一个无限的操作序列，每个小球的电荷量都收敛。

证明：显然，所有小球的电荷量的两两的差的绝对值之和递减。显然，若一次操作后，某个小球的电荷量变化量至少是某个常数，则上述和的减少量也至少是一个常数。因此若某个小球电荷量不收敛，则上述和会无限递减，这不可能。

引理2：从任意电荷量分配出发，对任意一个无限的操作序列，若这个操作序列满足，无论如何把全部小球分为两组，都有无限次操作使得分属两组的两个小球参与碰撞，则每个小球的电荷量都收敛到所有小球电荷量的平均值。

证明：若所有小球电荷量极限不全相等，则可以把它们分成两组，甲和乙，使得任何甲组小球的电荷量极限值大于任何乙组小球的电荷量极限值。充分多次操作后，小球电荷量都充分接近极限值，此时任何一次分属两组的碰撞都会导致被碰小球的电荷量改变一个常数，这不可能。

我们定义一种新操作：把至少两个(可以更多)电荷量不全相同小球碰在一块，使得电荷量平均分配。对这种新操作，同理有：

引理1'：从任意电荷量分配出发，对任意一个无限的新操作序列，每个小球的电荷量都收敛。

引理2'：从任意电荷量分配出发，对任意一个无限的新操作序列，若这个新操作序列满足，无论如何把全部小球分为两组，都有无限次新操作使得分属两组的两个小球参与碰撞，则每个小球的电荷量都收敛到所有小球电荷量的平均值。

引理1'与引理2'的证明与原证明几乎完全相同，此处省略。

引理3：从任意电荷量分配出发，对任意一个无限的新操作序列甲，存在一个有限的新操作序列乙，使得每个小球在甲操作序列下的电荷量极限值等于进行乙操作序列后该小球的电荷量。

证明：我们构造一个图，其顶点为全体小球。对任意两个小球，若在甲中存在无穷多次新操作，使得两个小球都参与了，我们就给两个小球对应的顶点连上一条边。

然后，若两个顶点之间有路径连接，我们就把它们连起来。这样我们就得到了一个新图，它是由若干个完全图作为连通分支组成的。

对甲操作序列，在有限多次新操作后，任何一次操作涉及的小球在图中都属于同一个连通分支。我们称这有限多次新操作为新操作序列丙。我们把乙取为，首先与丙一致，然后对图上的所有连通分支，若某个连通分支里的小球电荷量不全相同，就用一次新操作碰撞它们使得它们变为全相同。依次把所有连通分支都变为电荷量全相同。

由引理2'，乙操作序列结束后，每个小球的电荷量都为它在甲操作序列下的电荷量极限值。证毕。

给定一个小球的电荷量分配方式和一个实数。对一个有限的新操作序列甲，若其后可以接上其他有限的新操作序列(可以为空序列)，以使得有一个小球在操作后的电荷量能够任意接近或等于那个实数，我们就称甲(相对于电荷量分配和实数)是好序列。

给定一个电荷量分配与一个实数，若其对应的好序列存在，则从电荷量分配出发，每个好序列都产生一个新的电荷量分配，这个分配有一个方差。

引理4：给定任意电荷量分配和任意实数。给定一个好序列，则其后可以接另一个新操作序列，使得所得序列操作完成后有一个小球的电荷量恰为该实数。

证明：反设不能。设甲是反例。易知由甲后接序列得到的好序列可以通过再后接一步新操作得到另一个好序列。

由甲后接序列所得的好序列的方差会减少。我们给甲后接这样一个序列得到乙：我们恰好后接小球个数次操作得到乙，且让乙的方差尽量小。

从乙出发可以类似得到丙，以此类推，我们就得到了一个好序列的无限序列丁，它们可以组成一个新操作的无限序列戊。

根据引理3的证明过程，丁中存在一项，它可以通过后接不超过小球个数次操作得到戊的极限。然后可以在保持好序列的前提下随意走几步补齐操作次数。然后易知但此时它本应选择这个操作而不是原来的操作，矛盾。

证毕。

引理5：给定任意电荷量分配和实数，则以下两个命题等价：

1.存在有限长的旧操作序列任意接近该实数。

2.存在有限长的新操作序列取到该实数。

证明：由引理2，易从命题2推出命题1。

而若命题1成立，则对这个电荷量分配和这个实数，空序列是好序列。由引理4，它可以后接一个新操作序列直接取到该实数。

证毕。

现在回到原题。若存在一个区间，使得该区间中的二进制有限小数都能被一个有限长旧操作序列取到，则这个区间上的每个实数都能被一个有限长旧操作序列任意接近，从而被一个有限长新操作序列取到。但从一组有理数电荷量分配出发，使用有限长新操作序列后得到的电荷量也都是有理数，而任何区间里都有无理数，矛盾！

因此原题答案为否。

不存在。

我们把 个球上的电荷分布写成一个 维向量，那么两球相碰的操作就是一个 维实空间上的线性变换。为了下文的方便，在这里我们定义一个更一般的线性变换：将在非空集合 上做平均的操作记为 ，写成矩阵形式即

（我们用 表示矩阵 的 行 列的元素）

于是将 两球相碰的操作就可以记为 。

令 ，那么有限次碰球的操作就是有限个 中矩阵的乘积。我们知道所有的 阶方阵在矩阵乘法下构成一个幺半群，而上述的有限乘积就构成了 生成的子半群，记为 。由于初始向量是 ，经过矩阵M的变换就成为了M的第一列，所以原问题用抽象的语言表述就是：

证明集合 无处稠密（即闭包的内部为空）。

（ ^[1]证明了更一般的结论：给定任意有限个双随机矩阵，其生成的半群中的矩阵元素的集合无处稠密。本问题中要求的 是一个较简单的特例，但主要的思想是相同的。下面我们只对这个特例进行证明。）

既然要研究这个集合的闭包，我们不妨直接研究 的闭包。我们记 为 在欧式拓扑下的闭包，容易看到 本身也对矩阵乘法封闭。另一方面，注意到如下事实：

假设 ，且 在以 为边的无向图中连通，而 是一列矩阵，满足：

1. 每个 都是某个
2. 每个 都在 中出现无穷多次

则 。

一个直接的推论就是，每个 都在 中（当然只为证明 的话不需要这么麻烦，但上述事实我们在后面还会用到）。于是对于每个 ，下面的矩阵

都在 中。然而这个矩阵不仅满足 ，而且它是由 的值唯一确定的，并可以视为关于 的连续函数（一个简单的证明是通过注意到 是一个双随机矩阵，且其非 行、非 列都是相同的）。因此如果在 中有一列矩阵 使得 ，那么我们可以对应地在 中找出一列矩阵 ，使得极限 存在，且 ；而 显然本身也在 内，因为后者是闭集。

换而言之，每个集合 的极限点其实都是 中某个矩阵的元素。因此只要证明 是可数集，就可以导出 无处稠密。

事实上，我们可以证明 是有限生成的，其生成元就是全体 。记全体 的集合为 ，也即要证 。

前述的事实其实说明了对于任意一列 中的矩阵 ，其无穷积 都收敛到某些有限个 的乘积（从某个 开始，每个出现的 都出现无穷多次；所有出现无穷多次的 的下标构成的无向图中，每个连通分量 对应一个 ），也就是说 中的无穷积都在 中。

进一步地， 中的无穷积的乘积也都在 中，比如 。（虽然不能被写成 中的无穷积，但它也是 中的元素：对应于问题背景，它给出了 的电荷量，但不是通过无限次碰球操作不断逼近的，而是存在一系列的有限操作过程，每个过程的最终结果构成的序列逼近 。）

那么无穷积的无穷积，即 中的无穷积呢？这时我们把前述事实中所说的“边”替换成“超边”，结论是仍然成立的，即 中的无穷积也都可以写成 中的有限乘积。进而 中的无穷积的无穷积的无穷积，等等等等……都在 中。

为什么我们要考虑这些绕口令般的无穷积呢？这是因为这些无穷积总是收敛的，而它们都是构造 的极限点的手段。但从理论上来说， 的极限点可以对应任何有限乘积构成的收敛序列，完全可以和无穷积无关。我们接下来要做的就是从中“强行”找出无穷积的结构。

假设 中有一个序列，收敛到某个 ：

其中每个 都来自 。则要么对于足够大的 ， 最终都是 ，那么这个序列必然收敛到单位阵；要么就存在某个 ，使得它出现在无穷多行的开头（即等于无穷多个 ）。于是这个序列可以写成（下标举个例子）：

现在右侧的序列不一定是收敛的，但我们有紧致性，所以总可以找到一个收敛子列，于是又可以改写成（再举个例子）：

显然 乘上右侧序列的极限就是原本的极限，因此相当于我们从原本的序列左边“提”出了一个乘子 。现在右侧的序列要么收敛到单位阵，于是 ，我们一切搞定；要么我们就可以同上操作，从右侧提出一个新的乘子 （于是左边变成 ），并保证右侧新序列的收敛性（由于我编不出数字就不再举例子了）。接下来要么 于是搞定，要么又可以提出新的 放到左侧，等等等等……

上述的过程不一定会终止，但不终止的话我们实际上就在左侧写出了一个 中的无穷积 ，其极限是 中的元素，我们记为 。同时之前所有右侧序列的极限构成的集合一定存在一个聚点 ，容易证明 ，且我们总可以在右侧序列中出现过的所有有限积中找出一个收敛到 的子序列。

这一切意味着四个字：故伎重演！只要右侧的极限不是单位阵，我们就可以一直：

• 从右侧提出一个乘子放到左边；
• 如果堆积出了无穷多个乘子，就把它们“压缩”成 中的有限积；
• 这些 中的有限积也可能堆积出无穷多个，但它又成为了 中的无穷积，所以可以被继续压缩成 中的有限积；

在这个过程中我们始终保证左侧是 中的元素，右侧是一个 中的收敛序列，且左侧与右侧极限的乘积始终为 。

熟悉序数的读者应该已经看出这个过程与序数的关系了。如果没有看出来，下图可能会有帮助（来源：wikipedia）：

事实上利用超限归纳法，我们可以严格地将上述操作中的每一步用 中的序数编号。如果在 中存在某一步使得右侧极限是单位阵，那么左侧就是 ，证毕。假设不然，我们将证明左侧一定会出现 这个元素，而它是 阶双随机矩阵半群的零元，于是 ，一样完成任务。

为了让左侧出现 ，我们只需要保证左侧的 中的某些 能够阶段性地增大。注意到如下事实：如果 等于一列矩阵 的无穷积，那么 ，因而若 不完全相同，那么 。又注意到若 ，则 当且仅当 ，所以如果在某一个将左侧的无穷积压缩成有限积的步骤中出现了 完全相同的情况，就意味着我们从右侧提出的乘子“质量太差”，实际上全都会被左侧直接吸收。

解决办法也很简单，既然会被吸收，不如直接就在右侧把它们吸收掉：在上面过程的每一次提取乘子前，对右侧的每个有限积我们都抹去会被左侧吸收的最长前缀，而收敛性总可以通过找收敛子列解决。于是要保证的性质完全没有受到影响，并且左侧也不再会出现平凡的无穷积。这时就很容易证明左侧 的乘积中 的上极限会不断增大，直至达到 。

最后的这些步骤我写得比较hand-waving，严格的证明略为繁琐，且需要用到序数的康托范式，为了我的精神健康在此不具体写出，感兴趣的读者可以参考论文。

参考

1. ^[1] https://arxiv.org/abs/2010.16257