你在这里

三道趣题纪念数学游戏大师

第十届马丁•加德纳聚会(3月26日-4月1日)正在亚特兰大举行。马丁•加德纳是美国数学游戏界泰斗,在《科学美国人》杂志上曾开设了20余年的数学游戏专栏。他没有数学博士学位,但是他的谜题让无数读者不止一次燃起对数学的热情。加德纳于 2010 年 5 月 22 日去世,但以他命名的马丁·加德纳聚会仍在继续举办,这个聚会每两年在美国举行一次,与会者与加德纳的兴趣和爱好相同,多是数学家、魔术师和益智游戏爱好者。趁着这个时候,死理性派选择 3 个马丁·加德纳的趣味数学题,让我们一起来看看数学游戏大师的风采吧。

第十届马丁加德纳聚会logo:Gathering for Gardner 10
第十届马丁加德纳聚会logo:Gathering for Gardner 10

三角决斗的故事

汉密尔顿,普希金,伽罗华三个枪手A、B、C进行决斗,规则不同寻常:三人抽签决定开枪的顺序后,站成一个等边三角形,每人每次只开一枪,以抽签决定的顺序循环往复,直至只剩一人存活下来。每轮开枪的人可以瞄准任何人。虽然都是枪手,他们的命中率却各不相同。汉密尔顿百发百中,普希金命中率是 80%,伽罗华的命中率只有的50%。我们不考虑意外情况(比如子弹没打出去),如果他们三人都采取最佳的策略,那最后谁存活的概率最大?或者说三人幸存的概率分别是多少呢?

解答:

说来你可能不信,最后结果是枪法最差的伽罗华存活的概率最大,汉密尔顿的存活概率比普希金要高。这是因为,如果轮到汉密尔顿或者普希金开枪的时候,他们一定会向对方开枪,而伽罗华的最佳策略是对天开枪,直到汉密尔顿和普希金中的一个倒下(否则如果他射杀了某一个人,另一个人就要朝他开枪,两人都是高命中率,存活几率很小),接下来他可以先对剩下的那个人开枪,因此他最容易存活下来。

不妨让我们来具体计算一下每个枪手的存活概率:汉密尔顿的最容易计算,他和普希金的对决中,先开枪的概率(抽签决定)为 1/2,这时普希金会被杀死;普希金先开枪的概率也是 1/2,而普希金的命中率是 4/5,所以汉密尔顿对普希金幸存的概率是 1/2 + 1/2×(1 - 4/5) = 3/5,这时会轮到伽罗华开枪,如果伽罗华打不中,汉密尔顿会把伽罗华打死,因此,汉密尔顿从伽罗华枪下存活的概率是 1/2,所以汉密尔顿生还的概率是 3/5×1/2 = 3/10。

普希金存活概率的计算要复杂一些,它其实是个无穷级数。从前面的分析我们知道,普希金面对汉密尔顿的幸存概率为 2/5,而幸存后他会对上伽罗华,伽罗华打不中他的概率是 1/2,而普希金打中伽罗华的概率是 4/5,因此这时普希金存活的概率为 1/2×4/5 = 4/10,但是如果普希金没打中,这样伽罗华会获得第二次机会,普希金第二轮对上伽罗华的时候幸存概率为 1/2×1/5×1/2×4/5 = 4/100,以此类推,第三轮(如果有的话)普希金的存活概率为 4/1000,第四轮的时候为 4/10000……最终这个无穷级数的和为 4/10 + 4/100 + 4/1000 + 4/10000 + … = 4/9。所以普希金对伽罗华的幸存概率为 4/9,乘以之前他从汉密尔顿枪下生还的概率 2/5,普希金的生还概率为 2/5×4/9 = 8/45。

伽罗华的分析过程与普希金类似,或者用 1 减去汉密尔顿和普希金生还的概率,我们可以算出,他生还的概率为 47/90。 47/90 > 3/10 > 8/45,所以这场决斗枪法最差的伽罗华最可能获胜,其次是汉密尔顿,最后是普希金。不过更有意思的是,如果伽罗华没有那么明智,每轮都朝他认为的最危险的对手,百发百中的汉密尔顿射击,最终幸存的概率依然是三人中最高的,为 44.772%。但如此以来,另外两人的存活率就调了过来,普希金的幸存概率提升到了31.111%,百发百中的汉密尔顿幸存概率只有24.167%。或许现实中也是如此,高手总是死在笨蛋手里。

额头上的数字

图片来源:parallelozero.com
图片来源:parallelozero.com

教授有两个学生 A 和 B,他们都很诚实且有很强的推理能力。教授挑选了一对连续的正整数分别贴在他们的头上,两位学生可以看见彼此额头上的数字,但并不知道自己额头上的数字。教授开始不断问学生:现在你们知道自己额头上的数是多少了么?这样轮流不断的问,直至有人说“知道”为止。只过了一会儿,一个学生就回答“我知道了”。你明白他是怎样推断出来的么?

解答:

如果这一对连续的正整数中较大的数是 n,那么有一个学生会在教授的第 n 次或者第n-1次提问中回答“知道”(取决于教授先问哪个学生)。

我们利用数学归纳法来简单分析一下,首先从最简单的 1 和 2 开始,头上数字是 2 的人将在第 1 次或第 2 次提问的时候回答“知道”(如果他先被提问则是在第一次提问时回答,如果后被提问则是在第二次提问时回答),因为看到对方贴着1后,他会知道自己头上的一定是 2。

现在考虑 2 和 3 的情况。当第一次向贴着 3 的人提问时,他会说不知道,因为他看到对方是2时,自己头上的数字可能是1也可能是3。如果他是 1,这时他回答不知道后,贴着2的人就会知道自己是 2。但是他是3,所以轮到问贴着 2 的人回答不知道后(不清楚自己是 2 还是 4),第一个人就知道了自己贴的是 3,因此第二次向贴着 3 的人提问时,他将回答知道。

于是我们可以像这样继续推理,逐步推广到任何一对连续数字的情况。

对于这个问题,普林斯顿的数学教授 John Conway 有一个更加迷惑人的扩展。他将 n 个人头上贴上 n 个数字,这 n 个数字可以是任何一组非负整数,Conway又在一块黑板上写了一组数,这组数的个数小于或等于 n,且它们彼此不同,其中的一个数和之前贴在额头上的 n 个数字之和相等。假设参加者都是死理性派且很诚实,每人除了看不到自己额头上的数字,都能看到其他 n-1 个人额头上的数和黑板上全部的数。Conway向第一个人提问,问他能不能推断出自己额头上的数,如果他说不能,则接着问第二个人,如此循环往复,知道有人说知道为止。这个问题最终也会有人回答知道,实际上这个问题也可以用数学归纳法分析出来,有兴趣的读者可以自己试一试。

爱恨分明

图片来源:danlew.com
图片来源:danlew.com

有人的地方就有江湖,有人的地方就有爱恨。有这样 6 个物理学家,他们组成了一个特殊的小团体。在这个团体中,任何两人不是好友就是仇敌,并且团体中也没有彼此都为好友的 3 个成员。那么你能推断出他们中一定有 3 个成员彼此互为仇敌吗?

解答:

学过图论的同学对这题一定不陌生,这算得上一个经典的图论问题了。我们用六个小黑点 ABCDEF 来分别代表 6 个物理学家,再在各个黑点之间两两连上虚线。如果两个人互为好友,那么我们将代表他们的点之间的连接虚线涂成红色,如果互为仇敌,则把虚线涂成蓝色。则按照题意,没有3个人互为好友,则我们的图中不能出现 3 条边全为红色的三角形。而我们最终要证明,有3人互为仇敌,则图中一定有 3 条边全为蓝色的三角形。

不妨从 A 点开始说起, A 点与其他 5 个点有 5 条连接虚线,按照敌友原则对虚线涂上颜色后,至少有3条虚线的颜色是一样的,是什么颜色并不重要,是哪 3 条虚线也不重要。我们首先考虑是红色的情况:假定AB,AC,AD这3条虚线都是红色的,那么对于 △BCD,如果 BC、CD、DB 这三条边中有一条为红色,不妨设为 BC,那么 △ABC 的三条边均为红色,这与题意是矛盾的。同理,CD、DB也不能为红色。故而 △BCD 的三条边都只能涂成蓝色,这样 B、C、D 三个点代表的物理学家则为仇敌。接下来考虑AB、AC、AD这 3 条虚线都是蓝色的情况,对于 △BCD,因为不存在 3 条边均为红色的三角形,因此 BC、CD、DB 中一定有一条边是蓝色,不妨设为 BC,这样 △ABC 的三条边均为蓝色。
/gkimage/xk/3g/no/xk3gno.png
所以无论最初选的三条边是红色还是蓝色,我们一定可以在图中找到一个蓝色的三角形,它表示三个物理学家互为仇敌。

这个题目还有一个更加强的结论,如果图中没有 3 条边全是红色的三角形,那么一定会存在两个 3 条边全是蓝色的三角形。也就是说,这个 6 人小团体中,如果没有 3 个物理学家互为好友,则一定有 2 组 3 个物理学家互为仇敌的情况。这个结论的证明比上述的要略微复杂一点,脑力充沛的同学可以自己试试。

数学游戏就讲到这里,马丁•加德纳本人并不是一个数学家,他自己也在书里说过“如果要说我的书有什么意图,那就是引发大众对数学的兴趣。如果可以帮助外行人了解科学家们在做些什么的话,那么这种激励无疑是有必要的。真正的科学家还有更多的事情要忙呢”。他一生写过 50 本以上科普著作,把数学的趣味展现的淋漓尽致。

感谢马丁•加德纳,给我们带来不一样的数学之旅。

参考资料:

[1] 《科学美国人,趣味数学集锦》

[2] 《意料之外的绞刑和其他数学娱乐》

(来源:果壳网)