數(shù)學魔術(shù)系列之Kruskal的魔力

1、 發(fā)表于 2010-05-27如果你的朋友告訴你，他今天要跟你打個賭：他首先把一副撲克牌洗好，把除了兩個王以外的52張牌依次扣在桌面上，然后他把第二張牌翻開，是方片5，他向前數(shù)5張牌，翻開后，是梅花4，然后又向前數(shù)了4張牌，以此類推，每一次翻開的牌上面的數(shù)字是幾，就向前走幾步（j,q,k按1算）最后，當翻開紅桃5時，已經(jīng)接近牌的末尾，無法再向前數(shù)了。接著，他把除了最后翻開的紅桃5以外的所有牌都翻回去然后，同你講“你可以從第一張牌到第十張牌任意選一張開始，然后重復(fù)我的過程，如果你最后的一張牌也停在紅桃5，那么你就輸了，要給我100元；如果你的最后一張不是紅桃5，我就輸了，給你100元”。你敢跟你

2、的朋友打這個賭嗎？你可能會想，最后一張牌停在哪個位置有很多種可能性，最起碼倒數(shù)的十張牌都要可能，估計不會這么巧，我的最后的一張牌正好和我朋友的完全一樣，十有八九一百元錢歸我了。但是實際情況是，你的朋友是聰明的，十有八九要輸?shù)牟皇撬?，而是你?？催^蘇椰同學的生日悖論與生日攻擊（）的讀者都記得，經(jīng)過概率計算，在一個班50位同學中有相同生日的概率高達97%，遠遠高出了絕大多數(shù)人的意料。關(guān)于這個游戲的概率計算結(jié)果也同樣會令你大吃一驚。我們先來看一個例子，假設(shè)你選了從第一張牌開始，是梅花q,按照規(guī)則向前走一步第二張是方片5，你的朋友剛剛翻過的，到這里，你應(yīng)該猜得到，游戲不需要再進行下去了，你已經(jīng)輸了，因為

3、在這之后，你會完全重復(fù)你朋友翻牌的路徑，最后也終止于紅桃5。你或許會說，我應(yīng)該不會這么不幸吧，我翻開的第二張牌正正好好是我朋友翻過的。要是我不從第一張牌開始，從第三張牌、第四張牌、第十張牌開始，情況還會這么糟嗎？是的，你翻開的第二張牌不是你朋友翻過的牌的可能性還是很大的，可是以后向前翻牌的過程中只要有任意一張在你朋友走過的路徑上，你就輸定了。盡管對于翻開的某一個單張牌“中招”的概率不是很大，可是連續(xù)翻很多張牌都不“中招”就并非易事了。只有在整個過程中左奪右閃，小心翼翼，不掉進你朋友“設(shè)下的所有陷阱”，你才有可能贏得這個賭局。我們可以粗略估計一下你取勝的可能性首先，由于j,q,k都按1算，52張

4、牌的數(shù)字平均大小小于5，暫且按5計算，那么你從頭走到尾，平均要翻10張牌；然后，對于這十張牌，每一張的數(shù)字可能為1到10十種可能性，如果這張牌的數(shù)字“大小合適”，翻開的下一張牌就會落入朋友的陷阱,按照這張牌前面十張牌中平均只有一張是你朋友翻過的算（實際因為有很多張“1”，十張牌中會出現(xiàn)多于一張的“危險牌”），那么你一次生還的概率是9/10，最后，你久經(jīng)考驗、到了最后一張牌仍然和你朋友的紅桃5不重合的可能性就是9/10的10次方，只有35%。而如果考慮了“1”牌的因素，用更精確的方法計算的結(jié)果為15%左右，你朋友在這場賭局中有85%獲勝概率。也就是說，你的最后一張牌和你朋友的最后一張牌在大多數(shù)情

5、況下會是一樣的。這個數(shù)學小游戲最早由美國著名的應(yīng)用數(shù)學家martin david kruskal提出，被稱作kruskal count。很多人應(yīng)該都聽說過離散數(shù)學中的kruskal算法，martin david kruskal的弟弟joseph kruskal正是這一個算法的發(fā)明者。kruskal算法成了眾多電腦程序員不可或缺的武器，而kruskal count也成了眾多魔術(shù)師手中的法寶。由于一副撲克牌只有52張牌，如果把這個游戲當作魔術(shù)進行表演的話，仍然有百分之十幾的失手機會，但是如果用兩副、三副或更多撲克牌，失敗的可能性會降至很低（兩副撲克牌就可以降至5%）。除了用撲克，魔術(shù)師還可以要求你在長長的一篇英語文章中，從一個單詞開始，看這個單詞有幾個字母組成就向前越過幾個單詞，以此類推，一直到文章的末尾，然后魔術(shù)師會表演他的“讀心術(shù)”說出你停在的最后一個單詞。與這個紙牌游戲類似的一種用于破解密碼的計算機算法稱作波利德袋鼠算法。這個算法中，兩個數(shù)字的鏈條，被稱為“兩只袋鼠”，在解空間里面各自“跳躍”，其中一只為“馴化的袋鼠”，相當于你的朋友，它的參數(shù)都是確定的，而另一只為“野生的袋鼠”，相當于你，算法希望得到“野生的袋鼠”的參數(shù)。馴