華容道遊戲五直局兩將易位無解的證明

 

　　華容道遊戲有好些嚴格要求「對號入座」的玩法，兩將易位就是其中一種，具體玩法可見圖一的示例（這示例是要求僅是張飛和趙雲兩員大將交換位置，其他棋子保持在原位）：

 

圖一

 

華容道遊戲有一類佈局稱為「五直局」（或「無橫局」），即在佈局裡所有五個1×2的大將都豎放。本文將證明，這類五直局裡的兩將易位玩法都是無解的。

 

證明：

引理一

五直局裡，不存在「自由空間二」。（關於「自由空間二」，參見「華容道遊戲裡四種自由空間的公理」）

 

我們可以用歸謬法證明引理一。設若在「五直局」裡先安排好可讓兩兵兩將任意換位的「自由空間二（直立型）」，也就是兩小兵兩直將佔用去闊兩格高四格的空間，則餘下來的空位，要麼放得下曹操和兩員直將，餘下一員直將無處可放；要麼放得下三員直將，曹操卻放不下。顯見，這「自由空間二」在五直局裡是不可能存在的。引理一得證。

 

引理二

五直局裡的四枚小兵，不管怎樣移動，對五員大將和曹操之間的排列次序毫無影響。

 

理由：我們能夠而且僅能夠憑藉「自由空間二」，才能以小兵的幫助來改變某兩員大將的次序，使這兩員大將由順序變成逆序，又或由逆序變成順序。但由引理一，五直局裡並不存在「自由空間二」，這唯一的憑藉沒有了，所以小兵無論怎樣在棋盤內穿穿插插，都對五員大將和曹操之間的排列次序毫無影響。

 

　　由引理二，對於任一個五直佈局，都可以把它簡化，即把四枚小兵忽略掉，並把棋盤及棋子變形。具體方法見圖二的示例。

 

 

圖二

 

　　這樣簡化之後，就可以借鑒傳統的「十五棋子排列問題」（或稱「十五方塊」）的證明技巧來證明兩將易位無解。這裡首先需引入「逆序數」（又稱「顛倒數」、「反轉數」）的概念。「逆序數」的定義如下：「在一個以自然數（任二數皆不相等）組成的數列裡，當一對數字左邊小於右邊的為順序，則當一對數字右邊大於左邊的時候，便稱為逆序。逆序數就是這種數列裡，出現逆序的總對數。」易知，當一個數列是完全順序時，其逆序數是0。

 

　　從圖二的五直局簡化圖可知，華容道五直局的兩將易位相當於以下的遊戲形式：在高二格闊四格的棋盤內，有空格一個，不編號的1×2棋子一枚，編了號的1×1小方塊五枚。遊戲開始前，五枚有編號小方塊是完全順序的，現在要求藉着那個空格，把棋子移成僅有兩個有編號的小方塊交換了位置的新數列。當然，這個新數列還得依照初始狀態時棋子的排列形狀來排列。（參見圖三的示例，此示例是要求「3」和「5」交換位置，其他棋子位置保持不變。）

 

 

圖三

 

　　由五個數形成的數列，把其中兩個數交換位置，共有十種方法，不妨一一羅列成「表一」，並考察其逆序數：

 

表一

                12345

                1«2                21345              逆序數＝1

                1«3                32145              逆序數＝3

                1«4                42315              逆序數＝5

                1«5                52341              逆序數＝7

                2«3                13245              逆序數＝1

                2«4                14325              逆序數＝3

                2«5                15342              逆序數＝5

                3«4                12435              逆序數＝1

                3«5                12543              逆序數＝3

                4«5                12354              逆序數＝1

 

這十種兩數交換，逆序數都是奇數。

 

 

　　如圖三的示例，當棋子左右移動，並不會改變數列的逆序數，只有當棋子向上移或向下移的時候，逆序數才會改變。

 

　　其次，在這 2×4的棋盤上，有一枚不編號的1×2棋子，有五枚編了號的小方塊棋子能向上（或向下）移動，這樣只會而且僅會發生兩種模式，一種是交換一次，一種是連續交換三次（具體示例如圖四）。這一點，需要考察證明的情況是有限的，為求簡潔，這裡從略。

 

 

圖四

 

　　由於每交換一次，要麼逆序消失，要麼增加一個新的逆序，所以每交換一次，逆序數的增減為1。所以，當棋子在上述那類佈局裡向上或向下移，逆序數或是增減1次，或是增減3次，結果是原先的逆序數都會從奇數變為偶數或從偶數變為奇數。所以我們有：

引理三

                當棋子左右移動一格，逆序數不變

                當棋子向上（下）移一格，逆序數會由奇變偶或由偶變奇。

 

　　此外，我們還有

引理四

從初始狀態開始移動棋子，至若干步後移動棋子使之回復初始狀態時的棋子的排列形狀，則在整個過程裡，棋子上下移動的次數必是偶數。

 

引理四的證明：基於對稱性，只須考慮兩種情況，如圖五

 

 

圖五

 

　　在圖五的左方，棋子往下面的空格移動後，必須向上移一次，才能回復原狀，即上下移動的次數共是兩次，是偶數。再說圖五的右方，空格在左下方，先後把三枚棋子移動若干次，最後並回復空格在左下方的原狀，這種移法是每四步一個周期，比如是「下左上右」或「左下右上」，所以棋子上下移動的次數必是偶數。引理四得證。

                ★                    ★                    ★                    ★                    ★

 

　　回看如圖三所示的玩法，我們是從一個逆序數是0（偶數）的初始數列開始，通過棋子移動，移出表一所示的十種有兩數交換了的數列的其中一種，而它們的逆序數全是奇數。

 

　　由引理三和引理四，在這類佈局裡，無論怎樣移動棋子，當最後需要回復初始狀態的棋子排列形狀，棋子上下移動的次數必是偶數。換句話說，當回復初始狀態的棋子排列形狀，數列的逆序數的奇偶性會跟初始的時候相同。現在已知初始時逆序數0是偶數，所以當回復初始狀態的棋子排列形狀後，逆序數仍是偶數。這跟須移出一個逆序數是奇數的數列的玩法要求是矛盾的。故此，類似圖三的玩法要求是不可能有解的。也就是說：五直局裡的兩將易位玩法都是無解的。

 

證畢