逍遥学能 2015-02-15 13:28
一个国际象棋盘。是一个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所示：
分两种情形证明：(1)若起始点在A区，存在（2，3）马的马步哈密顿路，由于从A区的任一方格经一步（2，3）马，它可以到A区的一格或B区的一格；而由B区的一格经一步（2，3）马只能跳到A区的一格，注意到A区的方格数和B区的方格数是同样多的，所以必须从A区到B区，再由B区至A区的交替跳跃，才可能不重复地跳遍A，B两区。另一方面，我们把棋盘依黑白两色染色，如右图2所示：这样，从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区方格数相等相矛盾，定理证毕。