棋盤上的「馬步」探究

本文獲授權轉載自微信公眾號：無憂公主的數學時間（ID：wuyoushuxue），這是一個六年級小女生無憂公主的數學世界。在公眾號里，公主堅持每天一道難題，堅持寫原創文章，一年半的時間裡發布了500多道題，100多篇原創專欄文章。《棋盤上的「馬步」探究》是今年年初時，作為上海業餘數學學校的寒假作業而寫的一篇探究性論文，剛剛獲得了「上海市中學生數學探究性論文」的九年級組一等獎。論文以中國象棋棋盤中「馬走日字」為思考點，提出了五個與之相關的數學問題進行探究、推廣，非常棒的一篇探究性論文，分享給大家。（如需轉載請聯繫原作者）

0. 問題背景 （本課題為九年級組探究課題）

在中國象棋中，馬的走法是一直一斜，棋諺「馬走日字」（本質上說，「馬走日字」是走1×2 矩形的對角線）。從棋盤上任意一點出發，馬能跳到任意的一個點。

1. 在圖中半幅棋盤上，馬從點A出發，能否跳到任意的一個點？

分析與解答

我們將半幅棋盤的格點，抽象為5×9的方格矩陣，矩陣中的方格代表棋盤中的一個點。馬走「日」字相當於在矩陣中移動時，每一步的行號加減1且列號加減2，或者行號加減2且列號加減1。如果不考慮棋盤的邊界問題，每一步一共8種可能移動的方法。原題中的A點，就對應於矩陣中第5行第2列的位置。

為了解答這一題，我構造出了一條遍歷矩陣中所有方格的路徑，如下圖所示。起點為左上角，標號為1，每走一步標號增加1。這樣路徑軌跡上的標號，就形成了一個從1到45的序列。圖中標出了標號1到7的移動方向，作為示例。點A所在的方格，即圖中標號32的位置，也顯然在這條路徑上。從A出發，沿著這條路徑，不僅可以到達棋盤中的任意點，而且路徑上的方格也不會重複走到。

因此，馬從A點出發，是可以跳到半幅棋盤上的任意一點的。

另一種解法

這個問題的上述解法，是基於構造完成的，即構造出了一條遍歷所有節點的遍歷路徑。每個點只走一次的路徑，也叫做哈密爾頓路徑。我認為還有另一個解法可以討論。如下圖所示，從某一個節點出發，只需要跳 3 步，即可到達相鄰的位置。圖中給出了以左上角和中心點這兩個格子為起點的走法。這個操作所需的最大空間為3×4，所以半幅棋盤的空間足夠讓馬跳到相鄰的格子上。因此可以證明從任意方格出發，都可以在3步後到達相鄰的位置。那麼經過拓展，自然也就可以從任意方格出發，經過有限步，構造出一系列相鄰的方格為路徑，到達任意目標方格。所以起點為A時一定也能做得到，是這個結論的一個特例。

2.在圖中半幅棋盤上，馬從點A出發，能否跳遍半個棋盤，且每個點恰都只走到一次？

分析與解答

如下圖所示，我們將矩陣劃分為黑白間隔的樣式。馬每走一步，必然會跳到一個異色的方格，即從黑色的跳到白色的，或是相反。因此，馬跳過的任何一條路徑，必然是由黑白間隔的方格組成的序列。如果從任意白色方格出發，且途中每個方格只能經過一次，則整條線路上白色方格的數量必須等於黑色方格的數量，或者比黑色方格的數量大1。而半幅棋盤，總共有45個方格，其中黑色方格為23個，白色方格為22個。因此，從任意白色方格出發，包括A點，不重複地遍歷整個棋盤是不可能的。

3.半幅棋盤上，從哪些點出發，能跳遍半個棋盤，且每個點都只跳一次？

分析與解答

如上題解答中的分析，從任何白色方格出發，都不可能不重複地遍歷整個棋盤。而從任意黑色方格出發，遍歷整個棋盤，每個方格只走到一次，是可能的。接下來，我們要證明這不僅是可能的，而且確實有解。如下圖所示，棋盤中所有的黑色方格一共有23塊，因為對稱性，如果以其中用字母標出的這8塊方格為起點，可以分別構造出一條哈密爾頓路徑，則所有黑色方格都可以作為路徑的起點了。

下圖給出了以這8個黑色方格為起點的行走方案。所以，以圖中任何一個黑色方格為起點，都是存在一條哈密爾頓路徑的；而以任何一個白色方格為起點，是不可能做到的。

研究與拓展

上述分析的解法，證明了在5×9的矩陣中，從任何一個黑色格子出發，都存在一條哈密爾頓路徑。現在我做一個擴展：基於5×9的哈密爾頓路徑，可以擴展到無窮平面空間。也就是說，在無窮大的平面中，都存在一個哈密爾頓路徑。

如上面的圖6和圖7所示，我們構造一條路徑，從一個5×9的頂點位置（左下角）可以走到這個矩陣的上、下和右方的同樣一個5×9矩陣的頂點位置。這樣如果我們把一個平面空間抽象為無數個5×9 的矩陣平鋪而成的話，那麼就可以從一個頂點出發，採用「螺旋形」的走法，去遍歷所有的5×9矩陣。如下圖所示，如此走法，就可以構造出在無窮大的平面空間內的一條哈密爾頓路徑，即遍歷所有的方格，每個方格只走一次。

4.一個走「目」的「千里馬」在整幅棋盤上，能否從任意一點，跳到指定點？

分析與解答

如上圖所示，我們假設「千里馬」是一隻蟲子，每次走一個「目」字，都需要爬過4個格子，即從A向一個方向走3格，轉90°再走1格。這樣，從A出發的任何路徑上的每一個能走到的點，距離A的「距離」（即經過的格子數）都是4的倍數，即一個偶數。而從黑色格子（A）出發，終點為白色格子（B），必然需要經過奇數個格子。因此，走「目」字的千里馬，從A走到B是不可能的，並且這和棋盤的大小無關。

另一種解法

上述結論還有另一個解法，也比較容易理解。

如上圖所示，從一個黑色格子出發，下一步必然也在黑色格子中（即必然停留在同色格子內）。因此，無論如何都不可能從黑色格子走到白色格子，反之也一樣。

研究與拓展

那麼在10×9的整幅棋盤中，從任意一個位置出發，可以跳到的位置的範圍是如何的呢？下面我來證明在棋盤中，任意黑色的格子之間可以相互走到，白色的格子之間也可以相互走到。當然，前文已經證明了黑白之間是走不到的。

假設左上角的黑色格子為起點，我採用「寬度優先搜索」的演算法思想來構造走法。圖中左上角標號為1，圖中任意標號為i（i > 1）的格子，必然可以找到一個標號為i -1 的格子，通過千里馬走到它。實際上標號就表示為從左上角出發，能到達這個格子的最短步數。也就是說，如果從左上角出發，任意黑色格子，最遠只需要跳5步（最大標號6減去1）即可到達。

那麼從左上角出發，到每一個黑色格子的路徑，最終形成了一個樹狀結構，根節點（出發點）即為左上角的格子。對於任意兩個黑色格子，只要從其中一個格子出發，先到達兩個黑色格子的公共祖先（共同擁有的上級祖先），當然這裡最遠可以回到起點，然後再沿路跳轉下去就可到達另一個黑色格子。即任意兩個黑色格子之間，都存在路徑可以到達。

用類似的方法，我們來構造白色格子間的樹形結構。

如上圖所示，以第一行第二列為起點，遍歷結構和前文的黑色格子完全相同。同樣方法可以證明，任意白色格子間也可以相互走到。

綜上所述，把每個格子看作一個節點，將兩兩之間能跳到的格子間連邊，通過這樣的建圖的方式，整幅10×9的棋盤的90個節點的圖，實際上被構造成了兩個互不聯通的圖。一個由所有黑色格子構成，另一個由白色格子構成，兩個圖中兩兩可達（即強連通），但兩個圖之間沒有任何交集。

5.在一個無限大的棋盤裡，有一步能跳「1×n」的「飛馬」。怎樣的 n（n≥4），能使得它從任意一點出發，能跳到指定點？

分析與解答

我們分兩種情況進行分析，討論n的奇偶性問題。

類似於前文所述的「1×3」的飛馬，如果n為奇數，則「1×n」的「飛馬，必然只能在同色之間跳轉。此時，結論不成立，即不能從任意點出發，跳到任意點，且和棋盤的大小無關。

接下來，我來證明當n為偶數時，必然可以從任意點出發，跳到指定點。

首先，如上圖所示，不論n為多少（奇偶不論），從A出發，經過C點後必然可以走到相鄰的一個同色的格子。

當n為偶數時，從A出發第一步到達的格子顏色必然和A不同。此時，基於前文的結論，只需要沿著相鄰同色的格子走，必然可以達到A相鄰的那個異色的格子。如上圖所示，B1到B2，一直到Bk。那麼如果從任意格子出發，可以經過有限步達到相鄰的格子。則沿著相鄰的格子逐步迭代，就可以產生一條從A到無限平面中的任意位置的路徑了。

綜上所述，當n是偶數時，結論成立，即在一個無限大的平面里，飛馬從任意一點出發，能跳到指定點。（完）

歡迎大家走進一個六年級小女生的數學世界。>>>無憂公主的123篇原創專欄文章，收藏下來慢慢看哦！

每天好玩的數學

微信號：DailyMathFun

以數學學習為主題，以傳播數學文化為己任，以激發學習者學習數學的興趣為目標，分享有用的數學知識、有趣的數學故事、傳奇的數學人物等，為你展現一個有趣、好玩、豐富多彩的數學世界。

點擊展開全文

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！