Chinaunix首页 | 论坛 | 博客
  • 博客访问: 43370703
  • 博文数量: 4596
  • 博客积分: 58701
  • 博客等级: 大将
  • 技术积分: 48817
  • 用 户 组: 普通用户
  • 注册时间: 2006-02-22 16:58
个人简介

粵語歌文化歷史研究者,喜歡鑽研文字與音樂的創作,也喜愛數學與棋藝等等。

文章分类

全部博文(4596)

文章存档

2021年(5)

2020年(6)

2019年(9)

2018年(44)

2017年(84)

2016年(84)

2015年(119)

2014年(142)

2013年(205)

2012年(273)

2011年(307)

2010年(382)

2009年(429)

2008年(451)

2007年(779)

2006年(1277)

分类:

2011-02-16 07:36:08

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

 

圖一

 

華容道遊戲有一類佈局稱為「五直局」(或「無橫局」),即在佈局裡所有五個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是偶數,所以當回復初始狀態的棋子排列形狀後,逆序數仍是偶數。這跟須移出一個逆序數是奇數的數列的玩法要求是矛盾的。故此,類似圖三的玩法要求是不可能有解的。也就是說:五直局裡的兩將易位玩法都是無解的。

 

證畢

 

 

 

 

 

 

 

 

 

 
 
 
 
 
 
阅读(1841) | 评论(16) | 转发(0) |
给主人留下些什么吧!~~

黃志華2011-02-21 07:27:40

謝謝kk,我也不時會到貴博客瀏覽,見識很多華容道的變種玩法,美不勝收!  

黃志華2011-02-21 07:27:40

謝謝kk,我也不時會到貴博客瀏覽,見識很多華容道的變種玩法,美不勝收!  

黃志華2011-02-21 07:27:40

謝謝kk,我也不時會到貴博客瀏覽,見識很多華容道的變種玩法,美不勝收!  

黃志華2011-02-21 07:27:40

謝謝kk,我也不時會到貴博客瀏覽,見識很多華容道的變種玩法,美不勝收!  

黃志華2011-02-21 07:27:40

謝謝kk,我也不時會到貴博客瀏覽,見識很多華容道的變種玩法,美不勝收!