國際象棋中的數學問題

國際象棋中的數學問題

一個國際象棋盤，是一個8×8的64方格，歐拉曾研究過棋盤上馬的跳躍問題，他證明了，存在一個馬的跳躍路線，從一點出發，經過每一格一次且僅一次。最后又跳回到初始點。

上述的這樣一個馬步跳躍路線，稱為棋盤上的馬步哈密頓回路；如果不限制最后一步還要能跳回到始點，則稱為馬步哈密頓路。定義m，n是正整數，一個（m，n）馬，是指在一個充分大的棋盤上一步可縱橫跳m，n個格或n，m個格。于是，國際象棋的馬是（1，2）馬。下面給出一個定理，它刻畫了（2，3）馬和（1，2）馬的本質區別。定理從8×8棋盤上任一點出發，均不存在（2，3）馬的馬步哈密頓路。證把8×8棋盤分成A，B兩個區，分兩種情形證明：

（1）若起始點在A區，存在（2，3）馬的馬步哈密頓路，由于從A區的任一方格經一步（2，3）馬，它可以到A區的一格或B區的一格；而由B區的一格經一步（2，3）馬只能跳到A區的一格，注意到A區的方格數和B區的方格數是同樣多的，所以必須從A區到B區，再由B區至A區的交替跳躍，才可能不重復地跳遍A，B兩區。另一方面，我們把棋盤依黑白兩色染色，這樣，從A區的白（黑）格，經一步（2，3）馬，必到B區的黑（白）格，再從B區的黑（白）格經一步又回到A區的白（黑）格，如此下去，則只能跳過A區的白（黑）格和B區的黑（白）格，這和其存在（2，3）馬的馬步哈密頓路相矛盾。

（2）若起始點在B區，若存在著馬步哈密頓回路，則（2，3）馬不能交替地在B區與A去之間跳躍，否則歸約到情形（1）的類似證明。于是，存在一步且僅有一步從區到區的跳躍，這是因為A區與B區的方格數相等，從B區的方格經一步（2，3）馬必須跳到A區的緣故。考慮下面的3行，現考慮（2，3）馬在P，Q，R之間的跳躍。若P，Q，R均尚未跳過。有以下情形：（i）（2，3）馬首先跳到P點（首先跳到R的情形是類似的），由A，B區的構造，知必是A區跳到P點的。繼而由（2，3）馬從P至Q，Q至R.如果只不是最后一個未跳過的點。則下一步必須跳至A區的某一點。這樣就出現了在A區之間的2次跳躍，因此R就是最后一個未跳過的點。當R是最后一個未跳過的點時，則考慮點S，T，U之間的（2，3）馬的馬步跳躍。當先跳到S或U時，由上述討論可知，在S，T，U間會出現第2次從A區到A區的跳躍；當先跳到T時，由下述（ii）的推理知至少出現兩次從A區到A區的跳躍。

（ii）（2，3）馬首先跳到Q點，則（2，3）馬從Q至P，P必至A區，經若干步又由A區跳到R點，至少出現2次從A區至A區的跳躍。（Q先至R后到P，討論相同）

若從Q不跳到P或R點，它必跳到A區的某一點，則在以后的跳躍中，必然會出現一次從A區跳至P點，一次從A區跳至R點，同樣會出現至少2次的從A區至A區的跳躍。總之，至少存在著2步從A區至A區的（2，3）馬的跳躍，這與存在（2，3──馬馬步哈密頓路及A區，B區方格數相等相矛盾，定理證畢。