知讯网-财务分析、股票分析-专注管理、经营、创业、科技等资讯

标题: 三道趣题纪念数学游戏大师 [打印本页]

作者: zhixun 时间: 2012-4-1 06:31
标题: 三道趣题纪念数学游戏大师
果壳网：karsus 2012-03-31 17:25:03

第十届马丁·加德纳聚会即将结束。现在不知道点马丁·加德纳的东西还敢叫做数学爱好者吗？怎样在数学系博士面前假装见多识广？和他聊聊马丁加德纳的经典著作。
第十届马丁•加德纳聚会（3月26日-4月1日）正在亚特兰大举行。马丁•加德纳是美国数学游戏界泰斗，在《科学美国人》杂志上曾开设了20余年的数学游戏专栏。他没有数学博士学位，但是他的谜题让无数读者不止一次燃起对数学的热情。加德纳于 2010 年 5 月 22 日去世，但以他命名的马丁·加德纳聚会仍在继续举办，这个聚会每两年在美国举行一次，与会者与加德纳的兴趣和爱好相同，多是数学家、魔术师和益智游戏爱好者。趁着这个时候，死理性派选择 3 个马丁·加德纳的趣味数学题，让我们一起来看看数学游戏大师的风采吧。

第十届马丁加德纳聚会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
教授有两个学生 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
有人的地方就有江湖，有人的地方就有爱恨。有这样 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 的三条边均为蓝色。

所以无论最初选的三条边是红色还是蓝色，我们一定可以在图中找到一个蓝色的三角形，它表示三个物理学家互为仇敌。
这个题目还有一个更加强的结论，如果图中没有 3 条边全是红色的三角形，那么一定会存在两个 3 条边全是蓝色的三角形。也就是说，这个 6 人小团体中，如果没有 3 个物理学家互为好友，则一定有 2 组 3 个物理学家互为仇敌的情况。这个结论的证明比上述的要略微复杂一点，脑力充沛的同学可以自己试试。
数学游戏就讲到这里，马丁•加德纳本人并不是一个数学家，他自己也在书里说过“如果要说我的书有什么意图，那就是引发大众对数学的兴趣。如果可以帮助外行人了解科学家们在做些什么的话，那么这种激励无疑是有必要的。真正的科学家还有更多的事情要忙呢”。他一生写过 50 本以上科普著作，把数学的趣味展现的淋漓尽致。
感谢马丁•加德纳，给我们带来不一样的数学之旅。参考资料:
[1] 《科学美国人，趣味数学集锦》
[2] 《意料之外的绞刑和其他数学娱乐》

欢迎光临知讯网-财务分析、股票分析-专注管理、经营、创业、科技等资讯 (http://zhixun2010.com/)