打牌必須洗八次

拿一副52張的撲克牌，切成兩部分，然後將它們交錯疊成一副（又稱交錯式洗牌法）。連續洗8次，會發生什麼？

答案是這樣的：如果你使用最嚴格的洗牌法，那麼洗8次正好可以讓這副牌恢復成沒洗之前的排列。如果洗牌時帶有隨機性，那麼8次正好是能讓你洗勻這副牌的次數（註：一般其實說7次，不過根據對結論的解讀說8次也可以）。

這個答案我以前就有所耳聞。出於好奇，我去搜索了這兩個答案的證明法。作為一個數學系畢業之後很久沒碰正經數學的人，我被這兩個證明法、尤其是後一個的精妙打動了。所以，這期TIL對於數學恐懼的讀者們來說可能會很無聊。話說回來，即使對證明不感興趣，這兩個結論本身也是很有趣的豆知識。

——警告：以下內容包含數學證明，不想看的朋友可以直接去下一條分割線後點贊了——

問題一：洗多少次牌能洗回最初的排列呢？

完美洗牌的要求是切牌時完全嚴格地切成每副26張的兩部分（去掉大小王），然後將兩部分完美交錯地疊在一起。根據先疊哪一部份分為內外兩種：如果洗牌前頭尾兩張仍然在頭尾，稱為外完美洗牌法。如果頭尾兩張被洗到了第二張和倒數第二張，稱為內完美洗牌法。對於「8次恢復」來說，專指8次外完美洗牌法。如果把原始的52張牌編號成：

0 1 2 3 … 50 51

這樣的形式，那麼洗完一次以後會變成

0 26 1 27 … 25 51

這樣的排列。

這個變換有沒有簡單的描述法呢？是有的。洗牌前0-25號牌的編號乘以2，就是洗牌後的位置。而26-51號洗牌後的位置，則需要乘以2之後減去51。換言之，如果用f(x)代表x號牌洗牌後的位置，那麼

f(x)=(2*x)%51 <-------%代表除以51之後取餘數。

用公式表示以後洗兩次牌以後x的公式也可以算出來了：

f(f(x))=(4*x)%51

以此類推，洗8次牌就會變成

f(f(f(f(f(f(f(f(x))))))))=(256*x) %51

由於256除以51的餘數正好是1，所以上面這個式子正好等於x。換言之，洗8次牌之後，x號牌還是在x號的位置，回到了起點。

也正是因為此，這個「8次洗回去」的做法只對52張牌成立。如果使用54張牌的一副，就需要52次才能洗回去了，是不是感覺差距巨大……當然，如果允許使用內洗牌，還是可以用更少的次數來把54張牌的一副洗回去的。

問題二：洗多少次牌能洗勻呢？

這其實取決於我們對「洗牌法」的描述和對「洗勻」的定義。洗牌雖然是個直觀的過程，精確定義卻很難。對洗牌比較準確的描述是1955年提出的Gilbert-Shannon-Reeds模型——對，就是那個著名的香農。這個模型可以描述如下：

——對張數為n的一副牌，首先切上面的j張分給左手，剩下的分給右手，其中j由0到n的二項分布隨機決定。之後每次數左手和右手的牌。如果左手有a張，右手有b張，那麼以a/(a+b)的概率將左手這堆最下面的牌放到洗後牌堆頂上，否則將右手這堆最下面的牌放到洗後牌堆頂上。重複到雙手無牌為止。

定義完了洗牌，我們來考慮「洗勻」。52張牌洗完以後共有52!這麼多排列方式。如果每種排列的出現概率都是1/52!，那麼肯定是洗勻了，但是實際上肯定會有誤差。誤差越小，「洗勻程度」越高。數學上常用的一種描述兩個概率分布之間差距的方式叫全變差，就是把對應的每個事件的概率差絕對值加起來除以2，得到的結果越小，說明概率分布越接近。如果完全沒洗，那麼全變差會非常接近1。不過，如果你不喜歡全變差，想用另外一種方法計算誤差的話也沒關係，因為洗完後出現某種排列的概率是可以精確算出來的。

怎麼算呢？事實上，洗m次牌以後的洗牌法也是可以用類似的方法描述出來的。我們考慮「切成2堆洗牌」的一種推廣，「切成M堆洗牌」。這個過程可以用幾種不同的方法來描述，並且都是等價的：換言之，你問洗完以後得到某個排列的概率是多少，那麼這幾種方法得到的概率相同。

一、步驟描述：對n張的一副牌，選擇M個和為n的隨機變數j_1... j_M，符合多項式分布。按照順序將牌切成j_1...j_M張的堆。之後每次隨機選其中一堆的底牌放下，選某堆的概率正比於這堆的張數。直到所有堆都無牌為止。

二、最大熵描述：考慮切成M堆牌和將這M堆疊成一堆牌所構成的所有事件集合：也就是說，切牌方式不同而疊牌後結果相同的情況視為不同的事件。等可能地選擇其中一個事件。

最大熵描述的直觀表示：首先對洗後牌堆的n張牌分別隨機決定它是來自1-M的哪堆，並按照數目和順序將原始牌堆切成M堆。將這M堆的牌按順序放到洗後牌堆里。

三、幾何描述：以0到1之間的均勻分布獨立取n個數，並將它們按照從小到大順序排列成x_1... x_n。令y_i=M*x_i除以1的餘數。如果y_i在所有的y裡面是第j小的，那麼將第i張牌放到洗後牌堆的第j張去。

論文證明了這三種描述是等價的。並且根據幾何描述，「切成M_1堆洗牌」後再「切成M_2堆洗牌」等價於「切成M_1*M_2堆洗牌」。因此，「切成2堆洗牌」重複n次就等價於「切成M=2^m堆洗牌」。而計算洗成某種排列的概率需要利用最大熵描述：既然所有事件的概率一致，那麼洗成某種特定排列的概率正比於能產生這種排列的切牌法的數目。切牌法是有限制的：比如洗牌之前是1-52按順序排列，如果洗完的牌是9在8前面，那麼8和9必然在切牌的時候被分在了兩堆里。如果洗完的排列有r-1個逆序，就自然地把牌「切斷」成了r堆。將n張牌分成M堆（可能有空）並且逆序處至少有一個分割的方式共有C(M+n-r, n)種，而這除以總事件數M^n就是需要的概率。

由這裡開始，就可以在n=52的情況下計算洗牌次數不同的時候全變差是多少了。洗5次以下的時候全變差接近1，而洗6，7，8次牌時全變差分別是0.614, 0.334和0.167。洗8次牌就可以認為是洗勻了。當n趨近於無窮的時候，需要的洗牌次數接近1.5*log_2(n)。

從精確描述洗牌方式，到找到洗牌方式的等價表述，再到計算概率。整個證明一氣呵成神乎其技，令人不禁拍案叫絕。

———數學證明結束的分割線———

當然，實際打牌的時候，並不需要整副牌的排列重新分布得那麼均勻。而完美洗牌反而是一種會被各種魔術師和賭博漫畫使用的魔術手法。所以，如果有人堅持要在打牌前洗8次，那真的就要小心了。

PS：保證均勻的洗牌法是這樣的：先從52張牌裡面隨機選一張放到洗後牌堆頂上，再從剩下的51張裡面隨機選一張放去，以此類推直到所有牌放完為止。如果能保證每次選牌的時候是完全隨機的，那麼可以保證最後出現任何排列的概率都一樣。不過除了計算機以外，應該不會有人真的會這麼做吧……

cite：http://projecteuclid.org/euclid.aoap/1177005705

如果你喜歡這個系列的漫畫，點個贊吧！歡迎把它推薦給你的朋友，也歡迎關注公眾號TILcomic~