在中國象棋棋盤上，棋子「馬」從一個頂角走到斜對角最少需要七步，用數學怎麼證明？

01-28

我次奧、我突然想到能不能用馬爾可夫鏈來解決、、、等我熬夜給他搞出來

——————好了我回來了、、、歷時40分鐘、、、這速度考試要掛——————

首先，我們給每個坐標標個號，簡單粗暴地直接從左到右，再從下到上依次為1~90，自己腦補棋盤，所以對於某個坐標(i,j)，得到的標號是i+(j-1)*9;

NN.m:

function num=NN(i,j) num=i+(j-1)*9;

然後就是求轉移矩陣，有90*90矩陣p，記一步從a點到b點的概率記作p(a,b)，方法依舊簡單粗暴，兩個循環，看下一步幾個點符合要求，然後令下一步各點的概率平均。

main.m:

p(90,90)=0; for i=1:9 for j=1:10 n=0; if(i+1&<=9 j+2&<=10)n=n+1;end if(i+1&<=9 1&<=j-2 )n=n+1;end if(i+2&<=9 j+1&<=10)n=n+1;end if(i+2&<=9 1&<=j-1 )n=n+1;end if(1&<=i-1 j+2&<=10)n=n+1;end if(1&<=i-1 1&<=j-2 )n=n+1;end if(1&<=i-2 j+1&<=10)n=n+1;end if(1&<=i-2 1&<=j-1 )n=n+1;end if(i+1&<=9 j+2&<=10)p(NN(i,j),NN(i+1,j+2))=1./n;end if(i+1&<=9 1&<=j-2 )p(NN(i,j),NN(i+1,j-2))=1./n;end if(i+2&<=9 j+1&<=10)p(NN(i,j),NN(i+2,j+1))=1./n;end if(i+2&<=9 1&<=j-1 )p(NN(i,j),NN(i+2,j-1))=1./n;end if(1&<=i-1 j+2&<=10)p(NN(i,j),NN(i-1,j+2))=1./n;end if(1&<=i-1 1&<=j-2 )p(NN(i,j),NN(i-1,j-2))=1./n;end if(1&<=i-2 j+1&<=10)p(NN(i,j),NN(i-2,j+1))=1./n;end if(1&<=i-2 1&<=j-1 )p(NN(i,j),NN(i-2,j-1))=1./n;end end end

再接下來就是happy地不停p*p*p...了，p^n(a,b)即為n步從a到b的概率，具體證明請Bing:馬爾可夫鏈與轉移矩陣相關知識。反正什麼時候p^n(1,90)不等於零了，就說明n步可以從(1,1)走到(9,10)。

n=1;pp=p; while( pp( NN(1,1),NN(9,10) )==0 ) pp=pp*p; n=n+1; end n

最後答案：

樓上各位的答案均不夠嚴謹。

以棋盤左下角為原點，建立直角坐標系。問題要求從（0,0）到達（8,9）。

橫縱坐標移動總格數至少需要17格以上，每次行動移動格數為3，故達到目標所需的次數下界為6.

下說明6次是不可能的。

每次移動會造成橫縱坐標改變，且橫縱坐標之和的奇偶性必在移動後發生變化。

初始時橫縱坐標和奇偶性為偶，進行六次移動後，將變為偶，不可能如（8,9）這個點坐標和為奇。

再說明存在7次的方案，如依次經過（1,2），（3,1），（2,3），（3,5），（4,7），（6,8），（8,9)

故最小次數為7。

不好表述，想了半天拖到現在了。

先了解了下棋盤，左右8格上下9格(非專業勿噴)，就是說小馬同學要移動17格(左右+上下)到達目的地。小馬每邁一步能移動3格，數學老師告訴小馬要走17/3步(小馬不知道2/3應該算是0.66呢0.666呢還是0.6666…呢) 實際小馬要走至少6步。

假設小馬要走6步，那麼他將走過18格，誒，多出一格，怎麼辦？小馬想到一個辦法--「迂迴」。小馬半路上得溜達一圈(噠噠噠…) 。誒，又不對了，溜達出去還得溜達回來呀(如「凸」字形)，這樣小馬要「迂迴」就得額外走至少2格，18-2=16，小馬只能到宋冬野家，回不了草原。

如果小馬多走1步，總共走7步，他能移動21格。小馬在路上「迂迴」2格，算上回程(如」凸「字形)就有4格額外的路程，21-4=17，小馬就能回到草原了。

果然不好表述，舍友都睡覺了，中秋到了，節日快樂，拜拜。

蒙特卡洛法行不？