【文摘】国际象棋中的趣题妙解

一个国际象棋盘。是一个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

分两种情形证明:
(1)若起始点在A区,存在(2,3)马的马步哈密尔顿路,由于从A区的任一方格经一步(2,3)马,它可以到A区的一格或B区的一格;而由B区的一格经一步(2,3)马只 能跳到A区的一格,注意到A区的方格数和B区的方格数是同样多的,所以必须从A区到B区 ,再由B区至A区的交替跳跃,才可能不重复地跳遍A、B两区。 另一方面,我们把棋盘依黑白两色染色,如图2所示:

图2

这样,从A区的白(黑)格,经一步(2,3)马,必到B区的黑(白)格,再从B区 的黑(白)格经一步又回到A区的白(黑)格,如此下去,则只能跳过A区的白(黑)格 和B区的黑(白)格,这和其存在(2,3)马的马步哈密尔顿路相矛盾。
(2)若起始点在B区,若存在着马步哈密尔顿回路,则(2,3)马不能交替地在B 区与A去之间跳跃,否则归约到情形(1)的类似证明。于是,存在一步且仅有一步从区到区的跳跃,这是因为A区与B区的方格数相等,从B区的方格经一步(2,3)马必须跳到A区的缘故。考虑图1中下面的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区方格数相等相矛盾,定理证毕。

数学家俱乐部
数学趣题汇编
牛顿:在海边寻找贝壳的人
凯尔文:是上帝创造了生命,并且掌管一切
陆地动物能变成鲸吗
数学界的奇人妙事

Conway: 游戏人生
有关孪生素数的一个有趣猜想
素数之恋-伯恩哈德·黎曼
等分布理论简介
数学家波利亚
物理学之神奇的数
鸟和青蛙

此条目发表在数学, 游戏, 程序开发分类目录,贴了, , , 标签。将固定链接加入收藏夹。