不會洗牌的數學家不是好魔法師_風聞

　　在前一篇文章中，我們介紹了魔術師可以用洗牌來做什麼。但是，數學家在洗牌的時候會怎麼做呢？為此我們諮詢了來自西澳大利亞大學的教授謝麗爾·普拉格（Cheryl Praeger），普拉格主要從事羣論的相關研究——這是一個和對稱性相關的數學領域。普拉格2020年在艾薩克·牛頓研究所進行過一次相關話題的有趣討論。在她回到澳大利亞之後，我們和她有過交流，她向我們分享了一些關於羣論和洗牌的關係的迷人見解。

　　謝麗爾·普拉格

　　數學家利用完美洗牌可以做什麼？

　　我們首先來數一下通過洗牌操作可以產生多少種可能的置換。我們從一副k張牌組成的牌組開始，可以知道在洗牌操作之後，第一張牌所處的位置有k種不同的選擇。而留給第二張牌的空位只剩下了k-1個，留給第三張牌的空位只剩下了k-2個，以此類推。那麼所有可能的重排的總數是 k x (k-1) x (k-2) x … x 2 x 1**，**或者叫做 k的階乘，記作 k!。**k張牌組成的牌組的所有可能的置換構成了一個對稱羣，這個羣中的元素個數是k!。**舉個例子，對於6張牌構成的牌組，對稱羣中有720（6! = 6x5x4x3x2x1 = 720）種可能的置換。

　　而普拉格感興趣的則是通過完美洗牌（牌組被分成兩等份，洗牌之後牌被一張一張交疊在一起）能夠獲得的置換。完美洗牌有兩種方式：外洗法（第一張牌和最後一張牌位置固定）和內洗法（第一張牌和最後一張牌在洗牌之後都移動了一位），具體操作這篇文章有提到。我們考慮這兩種完美洗牌的方式的任意組合——你可以只做一次內洗操作，或者做三次內洗操作加一次外洗操作，再或者連續做八次外洗操作都可以。

　　這樣你通過所有的內洗操作和外洗操作的組合得到的卡牌的置換就構成了一個羣，我們叫它“洗牌羣”（shuffle group）。它並不包含牌組所有可能的置換。舉個例子，6張牌構成的牌組，它的對稱羣裏有720種可能的置換，而洗牌羣裏就只有24種。但是這兩個羣都有一個重要的數學特性。

　　威爾·休斯敦展示如何完美洗牌（來源：https://youtu.be/2TTrHmFC2bM）

　　洗牌羣

　　洗牌羣和對稱羣都有所謂的羣結構。從數學上講，羣****是以滿足四個規則的、以特定方式組合的對象（object）的集合（詳細信息可以看這裏)。例如，在我們的洗牌羣中，對象是由兩種類型的完美洗牌方式組合生成的洗牌。

　　洗牌羣是封閉的：如果您將羣中的任意兩個洗牌組合在一起，得到的洗牌也將是完美洗牌的組合，一般的洗牌羣也是如此。

　　每個洗牌都有逆元：一種洗牌再配上它的倒序洗牌，相當於沒有進行洗牌操作。例如，我們在上一篇文章對於一副52張牌的牌，一次外洗法，再配上連續7次外洗法，你就會回到原來的牌組順序。所以單次外洗的逆元是7次外洗組合起來。對於任何大小相等的牌組的洗牌羣和更大一點的對稱羣，都滿足作為羣的所有規則。

　　對於羣論學家來説，一個關鍵的操作是如何將一個有限的羣分解成它的基本組成部分——我們稱之為稱為單羣（simple group）。“通常你可以把一個羣分成兩部分，這樣每個部分都又構成一個羣，你可以繼續這樣做下去。”普拉格説，“它就像一棵樹的分枝，分枝後面還有分枝，直到得到一個不可能再分裂它的階段，這就像到了樹的葉子。當你找到樹上的葉子時，我們稱之為單羣，因為到了這一步它們就不能被進一步劃分了。”

　　以這種方式研究一個羣的話會發現很多有用的信息。比方説，你可以通過將樹上所有單羣的大小相乘來判斷羣的大小。“將一個羣分解成單羣是一個非常有用的工具，也是羣論學家首先要尋找的東西之一。”

　　中心對稱

　　一個早期的關於洗牌羣的有趣結論在20世紀80年代被數學家佩爾西·戴康尼斯（Persi Diaconis）、羅納德·葛立恆（Ronald Graham）和威廉·康特（William Kantor）所證明。“他們發現並解釋了一個非常優美的性質就是所謂的中心對稱性。”普拉格説，“你可以把這副牌中的最頂上和最底下兩張牌看作是是相互關聯的。在任何一系列完美的洗牌操作之後——假設最上面的牌移到了第三的位置，那麼最後一張牌就會升到倒數第三的位置——這是一種對稱性，無論對兩張牌中的一張做了什麼，另一張都會模仿它。”所以説，如果在一系列完美的洗牌之後，最上面的一張牌的位置在從上到下數的一個特定位置，那麼你就可以知道最後一張牌在從下往上數的同一位置。

　　戴康尼斯、葛立恆和康特的論文

　　每一對處在對稱位置的牌都會出現同樣的事情：位於牌組中心附近相同距離的兩張牌相互關聯，並且總是一起通過內洗或者外洗來移動。“一對牌被一同洗來洗去，就好像他們有某種無形的聯繫。而完全隨機的洗牌——不是這些完美的洗牌，則根本就沒有這種特性。”這種中心對稱性對洗牌羣中牌組的可能的置換產生了一些實際的限制。

　　戴康尼斯、葛立恆和康特證明了，對於具有中心對稱性的洗牌羣，它的單羣是非常受限制的。一個影響是對於於洗牌羣的大小，這取決於相關聯的單羣的大小。對於大多數的牌組，洗牌羣將是巨大的（這是相對於牌組中牌的數目而言的，儘管它比完全對稱羣要小得多）。而且通常洗牌羣的規模會隨着牌組中牌的數目呈現指數級增長。

　　如果你有一副6張牌，在它的洗牌羣中有24種可能的置換。一副10張牌的洗牌羣有1920個置換。一組26張牌的洗牌組中有超過25萬億種可能的置換。這些數字説明，洗牌羣的規模隨着牌組規模的增加呈指數級增長。

　　但是當牌組的規模大小是2的冪次時，一件令人驚奇的事情發生了，數學家稱之為****冪律特例（power case）。對於一套14張牌的牌組，它的洗牌羣中有超過32萬個置換。但是對於16張牌的牌組的洗牌羣——16張是24——只有64種可能的置換！一套30張牌的牌組就有千萬億（1015)種可能的置換，但一套32張牌組成的牌組——32是25——它的洗牌羣中只有160個可能的置換。當牌組的規模大小是2的冪次時，它會產生一個非常小的洗牌羣。

　　“這個冪次的例子真的是不可思議，”普拉格説，“在這種情況下，洗牌羣的大小要比典型的規模小了很多倍。”她解釋説，**在冪指數的情況下，洗牌羣的唯一組成部分是循環羣——**它們是最小的單羣。構建洗牌羣的模塊都如此之小，意味着洗牌羣也顯著地變小了：“所以沒什麼奇怪的！”(更多關於循環羣的信息可以看這裏)

　　一些有趣的工作

　　事實證明，類似的冪律特例也適用於“多手（many handed）完美洗牌”，這是普拉格與她的同事卡門·阿馬拉（Carmen Amarra）和盧克·摩根（Luke Morgan）在2019年探索過的。當他們訪問她的研究小組時，普拉格想起了一張藏在抽屜底部的、寫滿了舊數據的紙。“它在我的抽屜裏放了幾十年了！”現在正是研究一下的最佳時機。

　　這些數據來自於20世紀80年代肯特·莫里森（Kent Morrison）和約翰·坎農（John Cannon）為多手洗牌做的研究。想象一下，現在我們不是把一副牌分成兩個相等的牌堆，而是把它分成像三個相等的牌堆，然後把這三個牌堆完美地交織在一起。又或者我們把一堆東西分成四堆，或者七堆，或者十一堆，然後把這些等份的東西完美地混在一起。

　　“但是後來很多問題湧現了出來，”普拉格説。“你把牌分成k等分的牌堆——然後下一步呢？”你可以按照每個等份從牌堆上分開的順序，一次一張地從每一個等份的頂部拿起一張牌，這可能就像是進行外洗操作。但是換個方式，如果你決定從第二堆開始拿第一張牌，接着到第七堆拿一張牌，然後到第十五堆，再到第二十七堆呢！現在就有了很多可能的拿牌順序——當你有很多等分的小牌組時，什麼算是一次完美的洗牌？

　　普拉格和她的同事們決定用一種新的方式來思考多手洗牌的問題：他們不僅考慮了你將紙牌分成了多少堆，而且還考慮瞭如何指定允許的牌堆順序，這些順序決定了你在洗牌過程中交叉牌的方式。

　　他們將初始牌組的最上面一個等份標記為0，第二個等份標記為1，依此類推，第k個等份標記為k-1。然後他們就可以研究從牌堆中選擇牌的順序對最終洗牌時牌的重組的影響。

　　通過這種新方法，普拉格、阿馬拉和摩根證明了一個難題：在某些情況下，類似於冪律特例的事情也發生在這種多手洗牌中（感興趣的朋友可以看看這篇論文)。“在我和卡門還有盧克的這次合作中，我們把一副牌組分成k等份，每份有n張牌。我們觀察到，當小牌組的大小（n）是小牌組數目（k）的冪時，也存在類似冪律特例的特殊情況。這就像前面提到的2的冪次的標準情況：你又得到了一個非常非常小的洗牌羣。”

　　數學家們觀察到了這種多手洗牌中的冪律特例。同時也有一些實驗證據表明，在非冪律特例的情形下，洗牌羣似乎總要大得多。莫里森和另一位數學家史蒂夫·梅德韋傑夫（Steve Medvedoff）在一個猜想中指出，對於多手洗牌的情況下，非冪律特例的洗牌羣都將是巨大的。普拉格和她的同事們能夠用他們的新方法來證明這個關於非冪律特例的猜想。他們希望涵蓋將牌組分成任意數量的等份來進行多手洗牌的情況，從而更廣泛地證明這一猜想，但是這一過程中仍有許多開放性的問題亟待處理。

　　開放性的問題和新的視野

　　另外由於他們的新方法，普拉格、卡門和盧克能夠發現一些有趣的新結果。他們的新方法考慮到了在洗牌時牌堆的置換。特別是，他們發現“洗牌羣”保留了你允許的堆置換的許多性質。如果我們在允許的洗牌方式下定義一種牌堆的傳遞性的置換羣（這意味着你可以通過置換從一個順序的牌堆變到任意一個其他順序的牌堆）**，那麼你得到的“洗牌羣”也將是可傳遞的。**你可以用某一種洗牌的組合來把任何一張牌移動到牌堆的任何其他位置。這個傳遞屬性只是他們發現“洗牌羣”保留的一些羣屬性中的第一個。同樣，還有許多懸而未決的問題。

　　洗牌的數學是表現數學家如何工作的一個很好的例子。在這一情形下，他們從標準的紙牌遊戲中進行一次完美洗牌開始，將牌分成兩堆——我們已經知道有兩種類型的完美洗牌，即“內洗法”和“外洗法”。然後，在研究了這一設定的數學理論之後，他們又對設定和結論進行了外推：將牌堆分成三個、四個，甚至是任何數量相等的堆。他們從一張簡單的紙牌開始，起初可能只是是在桌上和朋友一起玩，但是，和往常一樣，他們不可避免地開始以數學的眼光看問題。

　　作者：Rachel Thomas

　　翻譯：Dannis

　　審校：zhenni

　　原文鏈接：

　　https://plus.maths.org/content/mathematics-shuffling