數學家們是怎麼玩趣味拼圖遊戲的?

2021-01-10 澎湃新聞

以下文章來源於中科院物理所，作者Bogdan Melnik

中科院物理所

物理所科研動態和綜合新聞；物理學前沿和科學傳播。

不變量理論是數學家在研究過程中很常用的一個分析手段。在實際問題中確定和尋找不變量以及可能的使用方法可以被看做為一門藝術，下面我們就從幾個小小的趣味問題入手，帶大家看看不變量的巨大作用。

數學史的淵源很深厚。追溯到4000多年前，我們在古巴比倫數學家的著作中就已經可以看出代數的痕跡了。根據相關歷史，我們可以確認，以那時的知識甚至可以求解經典的二次方程。

▲巴比倫泥板顯示了2的平方根的近似值（來源：Wikimedia ）

從那時起，數學就一直蓬勃發展，數學家們創造出了許多有用的數學工具。這裡數學家們所謂的「數學工具」是指用來構建數學邏輯的方法或者技術。之後，數學家們將這些數學邏輯合併為獨立的引理，之後又將引理轉化為定理。

也許，我們並不能列舉出數學中所有的邏輯和方法，但一些比較流行的方法還是可以舉出的，比如數學歸納法和反證法，大學一般都會普及這兩種方法。在這篇文章中，將會介紹另一種方法，這種方法很少被明顯地提及，但是卻足夠解決實際問題。

引入不變量

假設有一個數學對象x和一組變換T （變換代表對 x 進行某些操作），我們可以取集合T中的任何元素（即一個變換操作）並將其應用於x，來改變x的狀態。這樣，我們就可以形成x的不同態的鏈。

▲態的鏈

在這些概念的基礎上，我們的主角，函數I登場了。函數I可以代表x的任意狀態，比如說：它可以輸出任意自然數或者有理數集。對於不同的x，檢查I輸出結果是否相等是很重要的一件事。

現在，如果能證明將變換T作用到x上，函數I不改變它的值，則可以用這個事實來證明邏輯語句，並將I稱為由變換集T產生的對象x的不變量。

▲對於任何狀態鏈x，不變函數的值不變

讓我們考慮下面的示例，看看如何利用不變量來證明邏輯語句。

假想的群島

我們將從一個簡單的示例開始，然後嘗試緩慢地增加複雜性。

假設我們是生活在群島中某一片島嶼上的人。我們需要知道，如果沒有任何一個橋梁跟我們的出發點連接，我們就無法到達特定的島。

▲我們的虛擬小世界（圖源：Wikimedia）

我們能在自己所在的島嶼自由移動，但是橋梁只連接有限的島嶼，因此從一個島嶼不能到達所有的島嶼。

我們先將所有的島標號並用數字連接。

▲數字代表島嶼跟橋梁（i為島嶼，b為橋梁）

在上面的基礎上，引入不變函數I，將我們所在的島嶼編號輸入這個函數中，輸出的結果就是我們可能會到達的島嶼編號。

▲將島嶼和橋梁映射成數字後的世界示意圖

通過以上的示意圖，將I可能的輸出列舉出來為：

▲不變函數I的值

很明顯，在每個通過橋梁連接的「世界」中，我們任意沿橋梁移動並不會改變函數。那麼，一個人是否能夠從島嶼a到島嶼b？這個可以根據具體的函數I來決定。

▲根據函數I回答島嶼是否可達的問題

這就是關於不變量的一個例子，我們用它展示不變量的主要思想，接下來我們可以討論一些更有意思的例子。

象棋問題

假設我們有一個棋盤，這個棋盤有些不同——有人從同一對角線上的角落裡取下兩個格點。

▲奇特的棋盤

假想出這個棋盤的人同時給出了一個挑戰，並承諾挑戰成功的人能夠得到1萬塊：用2×1的多米諾骨牌填滿這個棋盤。

乍一看，這個問題似乎很簡單。從64個單元中去掉了偶數個格點，再拼放雙數單元的多米諾骨牌並不難。搞明白這個之後，我們可能會毫不猶豫地接受這個挑戰，畢竟，誰不想要1萬塊呢？

▲隨機填充的結果

筆者根據這個規則製作了這個遊戲的網頁版本，這樣我們就可以找到並證明這種可能性的存在。在網頁版本遊戲中請用滑鼠左鍵放置多米諾骨牌，用滑鼠右鍵改變多米諾骨牌的方向。

或者簡單一點，建議各位拿出紙筆，嘗試挑戰一下自己。

在一段時間的嘗試之後，我們可能會懷疑這種做法的可行性。下面讓我們利用不變量的想法來剖析這個問題。

首先，定義不變函數I為棋盤中未填充部分黑色和白色單元格數量的差異，這個函數的初始值為0，當從棋盤上移除兩個同樣顏色的格點後，值變為2。

其次，我們發現，任意放置一個多米諾骨牌總會覆蓋一個黑色和一個白色的單元格，所以無論放置多少個多米諾骨牌都不會改變之前定義的I值。

▲在放置多米諾骨牌時不變函數不會改變其值

現在可以看出其中的矛盾之處了麼？全覆蓋棋盤的I值應該為0，但是現在無論放置多少多米諾骨牌，I值都為2，不可能達到0.

哲學家馬克斯·布萊克在1946年出版的《批判思維》一書中提出了這個問題。

15格點的拼圖

19世紀末，山姆·洛伊德提出了另一個非常著名的謎題。作為一位美國象棋選手，他向世界發起挑戰，要人們來解決他的15個格點的拼圖問題（15 puzzle）。

▲15格點的拼圖遊戲

15個格點的拼圖遊戲本身是個智力趣味題，需要在棋盤上移動棋子使之按照1到15的順序回歸初始位置，這個的在線玩法也很容易找到。這個謎題在山姆·洛伊德提出的十年前就被提出了，但是，當洛伊德提出要提供1000美元作為獎金給解出15拼圖之後，這個遊戲才迅速在世界上傳播開來。

▲山姆·洛伊德最後兩塊交換後的拼圖（圖源Wikimedia）

山姆·洛伊德的版本有所不同，他從初始版本的拼圖開始，把14和15互換了位置。最終目的是一樣的：通過某種變換將其順序恢復到初始情況。

如何利用不變量來解決這個問題？我們來看一下。

我們先將拼圖排成一條直線。

▲將拼圖變成一條直線

接下來我們將每個單元格編號：

將原始拼圖中格點的移動映射到這條線上點的重排。

▲將拼圖中的移動映射到線上

對於這條線，我們可以計算逆序數，逆序數指的是：在一個排列中，如果一對數的前後位置與大小順序相反，即前面的數大於後面的數，那麼它們就稱為一個逆序。一個排列中逆序的總數就稱為這個排列的逆序數。（比如說：1 2 3 的逆序數為0，1 3 2的逆序數為1，3 1 2的逆序數為 2。）

對於從1到15的每個值v，我們應該計算從具有該值v的單元的位置i開始向右開始有多少個值小於v。

一個格點的逆序數，Ind 代表如果括號裡面是真的話輸出為1，反之則為0

計算所有格點的逆序數之和，得逆序數的和為：

▲逆序數之和

現在，我們來變個魔術。對於將全部的逆序數和空格點所在的行數相加所得的和總是偶數，這樣可以定義不變函數I。如果總和為偶數，I則為0，和為奇數，I為1。

▲在移動中，不變量保持不變

在這篇文章中可以找到不變量不變的嚴格解，其利用了置換的理論來證明。

經過以上分析，可以看出山姆·洛伊德的15拼圖中的不合理之處：如果交換相鄰的兩個格點而不改變空格點初始位置，逆序數將會增加1，因此I總會是奇數。這件事告訴我們，利用一般的方法是沒有辦法將拼圖恢復到原來的位置的。

我們能更進一步麼？

不變量的應用不僅僅局限於拼圖中。在現代數學中可以找到這種方法的很多應用：複分析、微分方程和其他理論。在實際問題中確定和尋找不變量以及可能的使用方法可以被看做為一門藝術，也許，這也是數學家們愛上這門學科的原因吧。