认真阅读下面的文章，并思考文末互动提出的问题，严格按照 互动：你的答案格式在评论区留言，就有机会获得由商务印书馆·涵芬楼文化提供的优质科普书籍《地表最强熊虫：不可思议的缓步动物》一本。

对于一个无模式可循的集合，很难掌握其规律，但数学家可以依靠简单的边界值来帮助回答他们心中的疑问。

躲雨或者休闲的时候，玩个简单的数字游戏打发时间吧！

咱们轮流从 {1,2,3,…,9} 这个列表中划掉数字，规则是不可以有3个连在一起的数字被划掉，先划到三连数字的人认输。

来吧！你可以先开始。

假设经过四步，我们划掉了这些数字：

又轮到你了。注意，如果你划掉4，你就输了，因为有3个被划掉的数字连在一起了：3-4-5。划掉7你也输了，因为是7-8-9。你只能划掉1，2或者6。但是无论你选其中的哪一个，我都可以通过再划掉另一个，让你没有可划的数字。

这是一个简单的游戏，但却用到了有趣的数学。一种方法是创造“缺口”，这样一来你的对手就没有别的选择，只能从中间补全一个“3连划”，就像这样：

另一个方法就是紧跟你的对手，迫使他们从左边或右边补全“3连划”，像这样：

不管你才用什么策略，有一件事情在数学上是确定无疑的：走过 6 步之后，必定有人会赢。这是因为从9个数字中划掉7个，必然会有3个被划掉的数字连在一起。（不信的话可以试试看，我们将在最后的练习中讨论这个问题。）在这种情况下我们说6是这个游戏中可走步数的“上限”。

所以，即使我可能不知道走哪步最好，但我们可以确定，这游戏最多玩不过6步就可以决出胜负。接下来我们可以拓展一下。将列表扩充为1-15的话，最多走10步可以出现赢家，概括来说，如果列表中数字个数可以被3整除的话，最多可以划掉2/3的数字。

找到这样的上限是理解游戏的一个步骤：例如，上限可能引导我们想出获胜的策略，或者当列表大小不是3的倍数时，上限可以作为一个参考量。虽然知道上限看起来并没有很大帮助，但相比于类似的规则的游戏，它已经是很大的进步了。

举个例子，我们把规则稍微改一下，3个划掉的数字不必都紧挨着，可以间隔一个固定长度。这意味着如果你划掉一个数字正好凑成2 3 4，你就输了（就像在原版游戏中一样），如果是1 3 5（间隔2）或者1 4 7，你也输了。这些模式是“等差数列”：间隔相同步长（称为公差）的数字序列。

回到我们第一盘游戏，使用新规则。还是轮到你，不过这次你已经输掉了。

划掉1会凑成1 3 5，划掉2凑成2 5 8，4凑成3 4 5，6凑成3 6 9，7凑成7 8 9。你走任何一步都会产生一个被划掉的等差数列。这里有很多可以注意的东西，这导致游戏比原版复杂得多，并且也更难找到安全步数的上限。

对于数学家来说，真正的乐趣在于把一个简单的数字游戏变成跟数学本身玩游戏。他们的目标是算出到底能走多少步就必然有人输掉，而且是在任意大小的数字串上。换句话说给定任意长度的数字序列，可以划掉多少数字而划掉的数字不形成一个等差数列？规则听起来简单的不能再简单，但是我们并不知道答案，并且我们对游戏的其他变化形式知道的更少。我们再玩几局游戏，看看数学会把我们领向哪里。

在我们的等差数列游戏中，一系列的“安全操作”其实本质上是一个“Salem-Spencer集”，即 {1,2,3,4,5,6,7,8,9} 中一个不含等差数列的子集。所以我们之前所说的上限实际上是对于我们这串数字最大的Salem-Spencer集。但是要知道走哪些步才能达到上限却很难办到。来看为什么。

我们从一个新的数字串开始。谁也不可能在头两步就输掉，所以随便选两个数字，直接划掉3和5。

然后选择第3个数字，这时候要注意了。就像原版游戏里一样，我们必须小心不要从已划数字的旁边或者中间做出等差数列。比如我们不能选4，因为3 4 5；不能选1，因为1 3 5 ，不能选7，因为3 5 7。因为8是安全的，所以就划掉它吧。

情况要变复杂了。现在要考虑的等差数列多了许多，我们要盯着三对划掉的数字。

一方面，我们对于将要发生的事情有很好的认识。对于每一对数字，我们都需要避免从中间或者旁边形成等差数列。但事情并不像我们希望的那样可以预测。一开始划掉的3和5消除了三个可能的选择：1，4和7。但是3和8不消除任何选择，因为我们必须避免的数字：-2，5.5和13并不在数字列表中。5和8只消除了2，因为6.5和13都不可选。

我们做出的每个选择都会消除一些未来的选择，但消除多少取决于我们选择什么数字。这一不规则性让穷尽所有可能性变得困难，我们也不再那么容易能够确定所有数字列表情况的上限了。

回到我们的游戏。我们看到6是安全的，所以我们划掉它。

游戏到此结束：下一步没有安全的选项了。我们已经知道1，2，4和7会输，划掉9会产生等差数列3-6-9。我们已经尽力了。

这意味着包含我们安全操作的集合 {3,5,6,8} 是一个 Salem-Spencer 集。但它是最大的吗？我们知道这个特定的集合不可能再大了，但是其他的策略可能产生更大的集合吗？{1,2,3,4,5,6,7,8,9} 可以包含更大而不含3项的等差数列的子集吗？

是有的：{1,2,6,8,9} 是此游戏的安全操作的集合，因此是一个Salem-Spencer集。并且是最大的。因为我们知道对于集合{1,2,3,4,5,6,7,8,9}，最大的Salem-Spencer集大小就是5。但是对于一般的n个元素的集合，{1,2,3,…,n}，我们不总是知道答案。事实上，对于现在来说，我们只知道 n ≤ 209 的答案。

数学家想知道，对于{1,2,3,…,n}，最大Salem-Spencer集中究竟有几个元素。但是总体来说他们能做到的最多只有确定一个范围。即使是这也非常困难，部分是因为我们上面看到的不规律性。划掉新数字可能消除许多选项，也可能只有几个。在下面的表格中，你可以看到这种不规律性。表格列出了对于{1,2,3,…,n}，不同 n 值下最大Salem-Spencer集中究竟有几个元素。

在我们 n = 9 的游戏中，最大的Salem-Spencer集的大小是5。但是注意到如果我加上10这个数字，最大Salem-Spencer集的大小并不增加，仍旧是5。

另一方面，n 等于12到13到14的情况下，最大值从6增加到7到8。但再增加1需要n增加6。

像Roth定理和 Szemeredi 定理这样的结果为这些集合和他们的变体的大小设置了界限，并且通常使用了大量数字和高等数学（比如遍历理论与傅里叶变换）。举例来说，菲尔茨奖得主蒂莫西·高尔斯在他关于更加广义的 Szemeredi 定理的工作中，为不含 k 长度等差数列集合的大小建立了一个重要的上限。但如果我们想计算我们游戏在 n = 9（数字列表的长度），k = 3（避免划掉的等差数列长度）时的上限，我们的计算会包含估算2的4096次方的大小，一个具有1200位的数字！

虽然这样的界限对我们的日常生活并不十分有用，但是对我们仍不能完全理解的集合，它给了我们一些数学上的掌控力。比如，直到最近我们还没有“多项式序列”的界限（即等差数列的推广，包括加法和升幂）。像2 + 3、2 +3²，2 +3³ 这样的多项式序列比简单的等差数列更复杂，从而使得选择不含多项式序列子集的游戏更难被理解。但建立上限是走向理解的另一步，这是每一个数字游戏的数学目标。

练习

Q：证明: 数字序列是{1,2,3,4,5}的原始规则的游戏中（连续划掉3个间隔为1的数字就输了），玩家1有一个获胜策略。

A: 若玩家1划掉3就可以稳赢。如果第二名玩家接着划掉1或5中的一个，第一名玩家划掉另外一个就可以获胜。如果玩家2划掉2，玩家1划掉5；如果玩家2划掉4，玩家1划掉1。

Q：数字序列是{1,2,3,4,5,6}的游戏中，任何一个玩家都有保证胜利的策略吗？

A: 玩家2有获胜的策略。假设玩家1从{1,2,3}中选择一个数字。则玩家2应从{1,2,3}中选择相邻的一个数字。例如，如果玩家1选择3，玩家2就选择2。接下来，玩家1就必须从{4,5,6}中选择一个数字。无论选哪个，玩家2都可以稳赢。如果玩家1最初选了集合{4,5,6}的数字，可以运用同样的策略。

Q：数字序列是{1,2,3,4,5,6,7,8,9}的原始规则的游戏中，不可能安全地走7步。

（提示：将数字序列分成以下子集：{1,2,3}，{4,5,6} 和 {7,8,9}。）

A: 注意，从提示中划掉三个子集中任何一个子集中的三个数字都将输掉游戏。走过6步之后，理论上我们可以在三个子集中的每一个子集中划掉两个数字。但无论第七步怎么走，都将连成3个数字而结束比赛。这被称为鸽子洞原则：把七只鸽子放进三个洞里，意味着至少一个洞里必须有三只鸽子。注意这与练习2中的获胜策略相似。

Q: 找到{1,2,3,4,5,6,7,8,9,10,11}的最大Salem-Spencer子集。

A: 一种策略是从两端的数字开始，因为它们永远不可能位于数列的中间。所以我们取1和11，这就排除了6。再次应用该策略选择2和10，这样3和9就不能再选了。从剩下的{4,5,7,8}中可以再取两个，比如4和5。根据上表，最大的Salem Spencer子集是6。

如需转载，请注明文章出处和来源网址：http://www.divcss5.com/css-texiao/texiao59293.shtml