數學魔術(2)Kruskal的魔力(組圖)

作者:Albert_JIAO 發表:2013-10-26 01:30
手機版 简体 打賞 0個留言 列印 特大

【看中國2013年10月26日訊】如果你的朋友告訴你,他今天要跟你打個賭:他首先把一副撲克牌洗好,把除了兩個王以外的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%)。除了用撲克,魔術師還可以要求你在長長的一篇英語文章中,從一個單詞開始,看這個單詞有幾個字母組成就向前越過幾個單詞,以此類推,一直到文章的末尾,然後魔術師會表演他的「讀心術」說出你停在的最後一個單詞。

與這個紙牌遊戲類似的一種用於破解密碼的計算機演算法稱作波利德袋鼠演算法。這個演算法中,兩個數字的鏈條,被稱為「兩隻袋鼠」,在解空間裡面各自「跳躍」,其中一隻為「馴化的袋鼠」,相當於你的朋友,它的參數都是確定的,而另一隻為「野生的袋鼠」,相當於你,演算法希望得到「野生的袋鼠」的參數。馴化袋鼠每次跳躍之後都會做一個陷阱,如果野生袋鼠的某次跳躍碰到了這個陷阱,則表明他們的參數是一致的。這樣,就可以使用馴化袋鼠的參數來推導出野生袋鼠的參數,與紙牌遊戲整個過程非常相似。



来源:科學松鼠會

短网址: 版權所有,任何形式轉載需本站授權許可。 嚴禁建立鏡像網站。



【誠徵榮譽會員】溪流能夠匯成大海,小善可以成就大愛。我們向全球華人誠意徵集萬名榮譽會員:每位榮譽會員每年只需支付一份訂閱費用,成為《看中國》網站的榮譽會員,就可以助力我們突破審查與封鎖,向至少10000位中國大陸同胞奉上獨立真實的關鍵資訊, 在危難時刻向他們發出預警,救他們於大瘟疫與其它社會危難之中。
榮譽會員

看完這篇文章您覺得

評論



加入看中國會員
捐助

看中國版權所有 Copyright © 2001 - Kanzhongguo.com All Rights Reserved.

blank
x
我們和我們的合作夥伴在我們的網站上使用Cookie等技術來個性化內容和廣告並分析我們的流量。點擊下方同意在網路上使用此技術。您要使用我們網站服務就需要接受此條款。 詳細隱私條款. 同意