數學魔術(2)Kruskal的魔力(組圖)
【看中國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位中國大陸同胞奉上獨立真實的關鍵資訊, 在危難時刻向他們發出預警,救他們於大瘟疫與其它社會危難之中。
看完這篇文章您覺得
- 【貫明專欄】臺灣最美的海灣 人間仙境七星潭(視頻)
- 水果皇后——草莓(組圖)
- 戰火無情 造化弄人 那一代人的離合滄桑(組圖)
- 千年前的人類抵禦矮人「他」化為惡龍(圖)
- 龍年龍抬頭地龍翻身 世界已現動盪不祥之兆(組圖)
- 世界上最貴的歌 4句歌詞火遍全球(組圖)
- 毛新宇預言中共2021年滅亡(組圖)
- 今菲熙比對聯再現 薄熙來案二審三大新看點(圖)
- 央行布局完畢 坐等房價下跌
- 賴昌星出來了! 與胡錦濤習近平之間的秘密曝光
- 爆周永康被查 央視傳遞高層動向(圖)
- 「電力一姐」「李公主」身陷醜聞 老底被揭(圖)
- 《看中國》近期將向中國大陸讀者推出翻牆破網服務
- 王岐山繼續高調反腐 大老虎他敢動嗎(圖)
- 中共肺炎(又称武漢肺炎)
- 病毒
- COVID-19
- 疫苗
- 台鐵
- 拜登
- 川普
- 特朗普
- 國安法
- 貿易戰
- 習近平
- 華為
- 三峽大壩
- 新疆棉
- 長江
- 洪水
- 袁弓夷
- 港版國安法
- 漢光演習
- 國民黨
- 退黨
- 弗洛伊德
- BLM
- 中共
- 閻麗夢
- 金正恩
- 王岐山
- 賴清德
- 孟晚舟
- 關稅
- 邊境牆
- 彭斯
- 美國
- 貿易談判
- 劉鶴
- 王滬寧
- 江澤民
- 崔永元
- 中南海
- 內幕
- 中共
- 反送中
- 貪官
- 情婦
- 腐敗
- 反腐
- 打虎
- 官場
- 看中國
- 一國兩制
- 法廣
- 社交媒體
- 往事微痕
- 出賣國土
- FB
- 六四
- 朝鮮
- 加拿大
- 脫歐
- 央行
- 債務
- 槓桿
- 美元
- 貨幣
- 人民幣
- 歐元
- 日元
- 港幣
- 房地產
- 樓市
- 財政
- 財富
- 中產
- 海參崴
- 台灣
- 蔡英文
- 北京
- 劉強東
- 大媽
- 房價
- 疫苗
- 非洲豬瘟
- 大陸
- P2P
- 霧霾
- 基因編輯
- 防火牆
- 維權
- 709律師
- 上訪
- 法輪功
- 網絡審查
- 活摘器官
- 江東六十四屯
- 唐努烏梁海
- 長白山
- 白龍尾島
- 江心坡
- SARS
- 新疆勞改營
- 言論自由
- 女主播
- 央視
- 華人
- 移民
- 華人
- 留學
- 海關
- 遣返
- 簽證
- 回國
- 入籍
- 綠卡
- 民生
- 海外
- 加拿大
- 澳洲
- 民國
- 桂軍
- 抗戰
- 孫中山
- 蔣介石
- 宋美齡
- 鄧小平
- 林彪
- 劉奇
- 中共
- 皇帝
- 諸葛亮
- 易經
- 幽默人生
- 智慧
- 感悟
- 手機
- 預言
- 奇聞
- UFO
- 外星人
- 壽命
- 文革
- 養生
- 紫鳳
- 貫明
- 李道真
- 軼飛
- 李雲飛
- 雲中君
- 辛思
- 夏聞
- 時代漫談
- 滄海
- 東方縱橫
- 唐柏橋
- 王尚一
- 江楓
- 黃清
- 李唐風
- 園丁
- 今濤拍暗
- 李青城
- 秦就石
- 中經研
- 秦天靖
- 江浩
- Eagle Vision
- 李子壬
- 馬新宇
- 馬來啟
- 紫君
- 秦山
- 陳破空
- 戴東尼
- 曹長青
- 邢仁濤
- 瑜正
- 簡易
- 肖川
- 伍凡
- 顧言
- 歸瑜
- 乙欣
- 陳泱潮
- 徐沛
- 鬼谷子的智慧:時來運轉「翻身術」(圖)
- 靈魂離開後再回來 死而復生的奇蹟(圖)
- 沒喝酒遭控酒駕 原來是這一「怪病」導致(圖)
- 愛崗敬業 無私奉獻 不准農民種地副書記(視頻)
- 你無法想像牆內底層的無恥與下賤(組圖)