第十二講棋盤中的數(shù)學(xué)(三)

1、第十二講 棋盤中的數(shù)學(xué)（三）棋盤對(duì)弈的數(shù)學(xué)問題我們看這樣一個(gè)比輸贏的問題.例1在8X8的棋盤格中的某個(gè)格子里已放入一枚棋子 “王”（如 下圖），甲、乙兩人輪流移動(dòng)“王”子，每次只能橫向或豎向移動(dòng)一 格.凡“王”子已經(jīng)占據(jù)過的格都不得再進(jìn)入.誰先遇到無法移動(dòng)“王” 子時(shí)，誰就算輸方.試證明，先走者存在必勝的策略.玉分析“王”子已占一個(gè)格，還剩下 8X 81= 63個(gè)格，比如甲 先走一個(gè)格，還剩下62個(gè)格.若能將62個(gè)格分成31對(duì)，每對(duì)都是 相鄰的兩小格，這時(shí)該乙走，乙領(lǐng)先進(jìn)入一格，甲就隨之進(jìn)入與其配 對(duì)的格，這樣就造成了甲必取勝的態(tài)勢(shì).因此，將64個(gè)格兩兩配對(duì)成為32個(gè)1 X 2的小矩形是解決本

2、題的關(guān)鍵.證明：設(shè)甲為先走的一方，在甲的心目中如上圖將64個(gè)方格兩兩配對(duì)分成32個(gè)1 X 2的小矩形，“王”子必在某個(gè)1X 2的小矩形的 一個(gè)格子中.甲先走，將“王”子走入這個(gè)1X2的小矩形的另一個(gè)格子中.這時(shí)還有31個(gè)1X 2的小矩形，每個(gè)小矩形中都有兩個(gè)小方 格.這時(shí)該乙走，乙總是領(lǐng)先進(jìn)入某個(gè) 1X2小矩形的第一個(gè)格，甲 就可以隨之進(jìn)入這個(gè)小矩形的第二個(gè)格.由于不能重復(fù)進(jìn)入“王”已 經(jīng)進(jìn)過的格子，所以乙總處于領(lǐng)先進(jìn)入新的小矩形的第一格的地位， 甲就總可隨之進(jìn)入這個(gè)小矩形的第二個(gè)格.最后必然乙先無法移動(dòng)“王”子，乙輸.甲必取勝.例2下圖是一盤未下完的中國象棋殘局，各子走法必須按中國 象棋的規(guī)

3、則辦事，將對(duì)方憋死或無法走子時(shí)算取得勝利.如果輪到乙 方走，問乙怎樣走法才能取勝？分析 這是中國象棋殘局，當(dāng)然各子的走法必須按中國象棋的規(guī) 則辦事，將對(duì)方憋死（無法走子時(shí)）算取得勝利。在上圖中，雙方的將（帥）均無法移動(dòng)，雙方的士（仕）也無法 移動(dòng)，底炮也不能在橫線上移動(dòng)（否則對(duì)方可將炮沉底打悶將）.底線兵（卒）只能橫向移動(dòng).誰先移動(dòng)底線兵（卒）打?qū)ⅲ瑫?huì)造成對(duì)方 將（帥）移出，從而出現(xiàn)移兵（卒）方自己必輸?shù)膽B(tài)勢(shì).因而只有底 炮、中炮和邊卒（兵）可以在縱線上移動(dòng)，兵（卒）只能前移 1步， 中炮只能前移4步，底炮只能前移8步.現(xiàn)在的問題是：乙先走，輪 流走完這三對(duì)子的13步，問乙怎樣走才能取勝？解:

4、我們把乙的獲勝策略及甲的各種走法列表于下 （其中“甲i, 乙i”分別表示“甲第一步走棋”與“乙第二步走棋”，其余類同；“中炮2,相炮3,卒1”分別表示“中路炮進(jìn)2步”,“相位炮進(jìn)3步”和“卒進(jìn)1步”.其余類同；“結(jié)果”欄表明乙i，甲1,乙i之后的態(tài)勢(shì)，其中的“距”以步為單位）：乙相炮M甲1|卒i相 炮！相 炮2中炮2梅炮？中炮i相炮4中炮4相炮中炮3相 1兵1中丸2相炮2中炮1相炮3中煙4相炮4中炮3相結(jié)果兵卒距01111中炮距42301相炮距43210其中，情形顯然為乙勝.情形，中，如甲2進(jìn)炮幾步,則乙3就將另一路炮進(jìn)同樣步數(shù)，這樣，終將乙勝.情形， 與，是類似的.以為例，甲的各種走法及乙的

5、策略見下表：甲2卒1相咆2中炮2相炮3中炮1乙3相炮1兵1中炮2相炮2中炮1相炮3結(jié) 果兵卒距011中炮距201相炮距210顯然，各種情形中也是乙勝.注意，若甲某次退炮幾步，則乙接著將同一路炮進(jìn)相同步數(shù)（這 樣，這兩只炮之間的間隔沒有改變）.說明：本題的深刻道理和規(guī)律在于自然數(shù)的二進(jìn)制表示， 將1步, 4步，8步分別用二進(jìn)制表示為1, 100, 1000.當(dāng)乙從8步中走了 3步后，變?yōu)檫€有5步即1, 100, 101.我們把這三個(gè)數(shù)寫成豎式11 0 01 0 1容易看出每一個(gè)數(shù)位上的數(shù)字之和都是偶數(shù) （這里均勿進(jìn) 位）無論甲怎樣走，所走的那一行的步數(shù)（用二進(jìn)制表示）至少有 一個(gè)數(shù)位上的數(shù)字發(fā)生

6、了變化， 從而破壞了上面的規(guī)律， 即不是每一 個(gè)數(shù)位上的數(shù)字之和都是偶數(shù)了，比如說，甲在中路炮進(jìn)一步，三路 的步數(shù)變?yōu)椋?1 11 0 1 這時(shí)三個(gè)數(shù)位上的數(shù)字之和 111，10，1 都不是偶數(shù) 乙再接著走，他的辦法是恢復(fù)上面的規(guī)律 這是能辦到的 首先， 他看一下數(shù)字和不是偶數(shù)的最高數(shù)位， 三路步數(shù)二進(jìn)制表示中至少有 一路在這數(shù)位上的數(shù)字是 1，然后，他就在這一路上走若干步，使得 上述數(shù)位上的數(shù)字和為 0，而較低數(shù)位上的數(shù)字為 1 或 0 以保證這些 數(shù)位上的數(shù)字之和為偶數(shù)，其它數(shù)位上的數(shù)字不變比如，對(duì)于上面 的情形，乙應(yīng)當(dāng)在“相”位炮所在的路線上走 3 步，將三路步數(shù)變?yōu)椋?1 1這樣繼續(xù)下

7、去，步數(shù)逐漸減少，必有結(jié)束的時(shí)候，由于甲走后, 不是每個(gè)數(shù)位上的數(shù)字之和都是偶數(shù)，所以甲不可能走到最后一步.走最后一步的是乙，所以乙必然取勝.例3如下圖是一個(gè)9X 9棋盤，它有81個(gè)小正方形的格子，在 右上角頂?shù)母褡永飿?biāo)有“”的符號(hào)代表山頂.A、B兩人這樣來游戲：由A把一位“皇后”（以一枚棋子代表）放在棋盤的最下面一行 或最左邊一列的某個(gè)格子里（即放在右圖中陰影區(qū)域的一個(gè)格子里）： 然后由B開始，兩人對(duì)奕：“皇后”只能向上，向右或向右上方斜著 走，每次走的格數(shù)不限，但不得倒退，也不得停步不前；誰把“皇后” 走進(jìn)標(biāo)有“”的那格就得勝.顯然，雙方對(duì)弈下去決不會(huì)出現(xiàn)“和棋”，在有限個(gè)回合后，必 有一

8、勝一負(fù)，試分析B必取勝的策略.這個(gè)游戲我們不妨稱之為“皇后登山”問題.分析 我們采用倒推分析的方法.如果 A把皇后走進(jìn)下圖中帶陰 影的格子，則B就可一步把皇后走到山頂而獲勝.因此任何一方都 應(yīng)該避免把皇后走進(jìn)右圖中的陰影地區(qū)， 而都應(yīng)該迫使對(duì)方不得不把 皇后走至帶陰影的格子里去，這是取勝的總的指導(dǎo)思想./ZA那么B應(yīng)把皇后走到哪些格子中才能迫使對(duì)方不得不把皇后走 進(jìn)上圖中帶陰影的格子里去呢？從上圖中可看出， 這樣的格子只有兩 個(gè)：有標(biāo)號(hào)和的格子.由此可知，如果誰搶占了或，只要走 法不再失誤，就必會(huì)得勝.因此，我們形象地稱、兩格為“制高 點(diǎn)”。那么為占或，如下圖，如果 A把皇后走進(jìn)有的方格里，

9、則B就能占領(lǐng)或，從而獲勝，而 B又怎樣迫使A不得不把皇后 走進(jìn)有的或有陰影的方格呢？同樣的分析可知，只要B能占領(lǐng)第二對(duì)制高點(diǎn)或即可。ZA*:*責(zé)*養(yǎng)7責(zé)*、*:.*T*%*4繼續(xù)運(yùn)用上述分析方法，還可以得到下一組制高點(diǎn)和.這時(shí)，不論A開始把皇后放在最左一列與最下面一行的哪個(gè)格 子中，B第一步都可以搶到一個(gè)制高點(diǎn)，或者第一步就直接達(dá)到, 只要走法得當(dāng)，必能穩(wěn)操勝券的.說明：1如果我們給出的是8X8的國際象棋盤，玩“皇后登山” 游戲，A開始把皇后放在最左列或最下行的哪個(gè)格時(shí)，A必勝？這時(shí)我們看到，對(duì)8X8棋盤，制高點(diǎn)在最左列上，制高點(diǎn)在最下列 上，所以A開始把皇后放于或，則 A必勝，放在其它格時(shí)，

10、B 可搶到制高點(diǎn)，則B必勝.2. 如果在普通的圍棋盤上，（共有18X18 = 324個(gè)格）玩“皇后 登山”游戲.B取勝的制高點(diǎn)都是哪些？請(qǐng)讀者自己找出來.可以告 訴大家，一共有六對(duì)，計(jì)12個(gè)制高點(diǎn).例4在8X8的國際象棋盤中（如下頁圖）有三枚棋子，兩個(gè)人 輪流移動(dòng)棋子，每一次可將一枚棋子移動(dòng)任意多格（允許兩枚或三枚棋子在同一格），但只能按箭頭所表示的方向移動(dòng).在所有棋子都移 到A點(diǎn)時(shí)，游戲結(jié)束，并且走最后一步的算贏，問哪一個(gè)人能夠獲 勝？OOA解：由三枚棋子到A的格數(shù)分別要走59步，50步和30步，這 樣就與例2在三條路線上走步本質(zhì)上一樣的，我們不妨把 59, 50, 30這三個(gè)數(shù)寫成2進(jìn)制.

11、59=( 111011) 2, 50=( 110010) 2, 30=( 11110) 2排在一起：1 1 1 1 0第一個(gè)人應(yīng)當(dāng)將第一行的111011改為101100,也就是減少1111,這樣就使各個(gè)數(shù)位上的數(shù)字和為偶數(shù).這時(shí)無論第二個(gè)人如何走都將 破壞這個(gè)特性，第一個(gè)人接著可以采取使各個(gè)數(shù)位上的數(shù)字和為偶數(shù) 的方法，穩(wěn)步地走向勝利這就是說，第一個(gè)人應(yīng)當(dāng)將最外面的棋子移動(dòng)15 步（即（1111）2= 1X 23+ 1X22+ 1 X 2+ 1 = 15）,即可按例2的規(guī)則穩(wěn)步取勝。習(xí)題十二1.如下頁圖是一個(gè)3X 101的棋盤，甲每次可走一個(gè)黑子，乙每次可走一個(gè)白子.每枚棋子只能在它所在的行沿固定方向移動(dòng)，走步數(shù)不限，但不能越過對(duì)方棋子，誰不能走子誰算輸.若甲先走，請(qǐng)指 出甲必取勝的著法.甲 Ab B 乙2. 對(duì)8X 8的棋盤，討論“皇后登山問題.3. 在普通圍棋盤上（共18X 18= 324個(gè)格）討論“皇后登山” 游戲.4. 圖a是一個(gè)彩色激光棋盤，上面有紅（打X）黃（空白格）藍(lán)（斜線格）三種顏色的方格.游戲人可以隨意地通過按電鈕將某一 行或某一列的小方格同時(shí)改變顏色，紅變黃，黃變藍(lán)，藍(lán)變紅，如果 按不多于10次電鈕將圖a變?yōu)閳Db,便可得獎(jiǎng).問游戲人能否