洗牌

       90年度寒假的前一天,教育部在台北縣板橋火車站推出「教學創新九年一貫影像紀錄暨推動成果」博覽會,當天曾志朗部長於開幕後,親自示範一場教學觀摩,課堂裡,他問同學「一副撲克牌要如何洗乾淨?」這倒讓我想起一道曾經難倒過不少數學家的問題:「一副撲克牌要洗幾次,才可以洗乾淨?」一副牌可能的排列組合有52×51×50……×1,大約是1068種,這個數字比古印度國王無知而答應獎賞西洋棋發明者--希薩的麥子還多得多。希薩要求印度國王賞他麥子,只要在棋盤的第一小格內放置一粒,第二小格子內放兩粒,第三小格子內放四粒……,依此類推,每一小格內的麥子數都是前一格的2倍,麥子的數目是264-1 =18446744073709551615,就算整個印度倉庫裡的所有麥子全部賞給希薩還是不夠,甚至全球所有麥子的收獲,也不夠給賞的。

       一副撲克牌要洗幾次,才可以洗乾淨呢? 美國哈佛大學數學家岱科尼斯哥倫比亞大學數學家貝爾,為了解開這問題,曾長期觀察人們玩牌的洗牌方式,最後他們發現一種有效洗牌方式--彈洗--將牌分成兩半、交互切入的洗牌法,他們把52張牌編上號碼,並由1到52遞增排列。洗牌時,將牌分成兩疊,有一疊牌是1到26,另外一疊則由27到52。彈洗一次牌後,會出現這樣的排列:1,27,2,28,3,29……,也就是兩組遞增的數列混在一起,一組是1,2,3....26.;另一組是27,28,29.......,52。第二次彈洗牌後,會出現這樣的排列:1,14,27,40,2,15,28,41,3,16,29,42,也就是四組遞增的數列混在一起,一組是1,2,3....13;一組是14,15,16....26;一組是27,28,29....39;一組是40,41,42....52。如果繼續彈洗到第七次,遞增數列可達26組,這副牌幾乎就看不出原來的順序了,也就是說一副撲克牌彈洗7次就洗乾淨了。

       後來,英國牛津大學的數值分析教授Lloyd N.Trefethen和父親Tufts University大學的機械工程教授Lloyd M.Trefethen一同分析研究了許多副牌,根據他們的研究報告,一副按順序排列、還沒洗過的牌中,總共包含了225.58bits的資訊,這些資訊將會在洗牌過程中逐漸被洗淨掉。Trefethen父子利用電腦程式來彈洗這些牌,發現到第一次彈洗後,牌堻173.58 bits的資訊;第二次彈洗後剩121.58bits的資訊,不過要讓牌混亂化,其實只要彈洗五或六次就夠了。彈洗六次後,這副牌就洗掉99%的資訊了。

彈洗數 0 1 2 3 4 5 6 7 8 9
bits 225.58 173.58 121.58 69.874 27.271 7.9452 2.0727 0.5239 0.1313 0.0329
洗淨度 0% 23.1% 46.1% 69.0% 87.9% 96.5% 99.1% 99.8% 99.9% 99.99%

上表資料來源:How many shuffles to randomize a deck of cards? (pdf)---Lloyd N.Trefethen


Copyright ©2002昌爸工作坊 all rights reserved