认真阅读下面的文章,并思考文末互动提出的问题,严格按照 互动:你的答案格式在评论区留言,就有机会获得由商务印书馆·涵芬楼文化提供的优质科普书籍《地表最强熊虫:不可思议的缓步动物》一本。
对于一个无模式可循的集合,很难掌握其规律,但数学家可以依靠简单的边界值来帮助回答他们心中的疑问。
躲雨或者休闲的时候,玩个简单的数字游戏打发时间吧!
咱们轮流从 {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