国际象棋中的数学问题
国际象棋中的数学问题
一个国际象棋盘,是一个88的64方格,欧拉曾研究过棋盘上马的跳跃问题,他证明了,存在一个马的跳跃路线,从一点出发,经过每一格一次且仅一次。最后又跳回到初始点。
上述的这样一个马步跳跃路线,称为棋盘上的马步哈密顿回路;如果不限制最后一步还要能跳回到始点,则称为马步哈密顿路。定义m ,n 是正整数,一个(m ,n )马,是指在一个充分大的棋盘上一步可纵横跳m ,n 个格或n ,m 个格。于是,国际象棋的马是(1,2)马。下面给出一个定理,它刻画了(2,3)马和(1,2)马的本质区别。定理从88棋盘上任一点出发,均不存在(2,3)马的马步哈密顿路。证把88棋盘分成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 区方格数相等相矛盾,定理证毕。