神马文学网数学魔术系列之Kruskal的魔力
来源：百度文库 编辑：神马文学网 时间：2024/04/28 07:54:55
如果你的朋友告诉你，他今天要跟你打个赌：他首先把一副扑克牌洗好，把除了两个王以外的52张牌依次扣在桌面上，然后他把第二张牌翻开，是方片5，他向前数5张牌，翻开后，是梅花4，然后又向前数了4张牌，以此类推，每一次翻开的牌上面的数字是几，就向前走几步（J,Q,K按1算）……最后，当翻开红桃5时，已经接近牌的末尾，无法再向前数了。
接着，他把除了最后翻开的红桃5以外的所有牌都翻回去
然后，同你讲“你可以从第一张牌到第十张牌任意选一张开始，然后重复我的过程，如果你最后的一张牌也停在红桃5，那么你就输了，要给我100元；如果你的最后一张不是红桃5，我就输了，给你100元”。你敢跟你的朋友打这个赌吗？
你可能会想，最后一张牌停在哪个位置有很多种可能性，最起码倒数的十张牌都要可能，估计不会这么巧，我的最后的一张牌正好和我朋友的完全一样，十有八九一百元钱归我了。但是实际情况是，你的朋友是聪明的，十有八九要输的不是他，而是你。
看过苏椰同学的《生日悖论与生日攻击》（http://songshuhui.net/archives/23737.html）的读者都记得，经过概率计算，在一个班50位同学中有相同生日的概率高达97%，远远高出了绝大多数人的意料。关于这个游戏的概率计算结果也同样会令你大吃一惊。
我们先来看一个例子，假设你选了从第一张牌开始，是梅花Q,按照规则向前走一步
第二张是方片5，你的朋友刚刚翻过的，到这里，你应该猜得到，游戏不需要再进行下去了，你已经输了，因为在这之后，你会完全重复你朋友翻牌的路径，最后也终止于红桃5。你或许会说，我应该不会这么不幸吧，我翻开的第二张牌正正好好是我朋友翻过的。要是我不从第一张牌开始，从第三张牌、第四张牌、第十张牌开始，情况还会这么糟吗？是的，你翻开的第二张牌不是你朋友翻过的牌的可能性还是很大的，可是以后向前翻牌的过程中只要有任意一张在你朋友走过的路径上，你就输定了。尽管对于翻开的某一个单张牌“中招”的概率不是很大，可是连续翻很多张牌都不“中招”就并非易事了。只有在整个过程中左夺右闪，小心翼翼，不掉进你朋友“设下的所有陷阱”，你才有可能赢得这个赌局。
我们可以粗略估计一下你取胜的可能性
首先，由于J,Q,K都按1算，52张牌的数字平均大小小于5，暂且按5计算，那么你从头走到尾，平均要翻10张牌；
然后，对于这十张牌，每一张的数字可能为1到10十种可能性，如果这张牌的数字“大小合适”，翻开的下一张牌就会落入朋友的陷阱,按照这张牌前面十张牌中平均只有一张是你朋友翻过的算（实际因为有很多张“1”，十张牌中会出现多于一张的“危险牌”），那么你一次生还的概率是9/10，
最后，你久经考验、到了最后一张牌仍然和你朋友的红桃5不重合的可能性就是9/10的10次方，只有35%。而如果考虑了“1”牌的因素，用更精确的方法计算的结果为15%左右，你朋友在这场赌局中有85%获胜概率。也就是说，你的最后一张牌和你朋友的最后一张牌在大多数情况下会是一样的。
这个数学小游戏最早由美国著名的应用数学家Martin David Kruskal提出，被称作Kruskal Count。很多人应该都听说过离散数学中的Kruskal算法，Martin David Kruskal的弟弟Joseph Kruskal正是这一个算法的发明者。Kruskal算法成了众多电脑程序员不可或缺的武器，而Kruskal Count也成了众多魔术师手中的法宝。
由于一副扑克牌只有52张牌，如果把这个游戏当作魔术进行表演的话，仍然有百分之十几的失手机会，但是如果用两副、三副或更多扑克牌，失败的可能性会降至很低（两副扑克牌就可以降至5%）。除了用扑克，魔术师还可以要求你在长长的一篇英语文章中，从一个单词开始，看这个单词有几个字母组成就向前越过几个单词，以此类推，一直到文章的末尾，然后魔术师会表演他的“读心术”说出你停在的最后一个单词。
与这个纸牌游戏类似的一种用于破解密码的计算机算法称作波利德袋鼠算法。这个算法中，两个数字的链条，被称为“两只袋鼠”，在解空间里面各自“跳跃”，其中一只为“驯化的袋鼠”，相当于你的朋友，它的参数都是确定的，而另一只为“野生的袋鼠”，相当于你，算法希望得到“野生的袋鼠”的参数。驯化袋鼠每次跳跃之后都会做一个陷阱，如果野生袋鼠的某次跳跃碰到了这个陷阱，则表明他们的参数是一致的。这样，就可以使用驯化袋鼠的参数来推导出野生袋鼠的参数，