2015-07-24 收藏
一个国际象棋盘。是一个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区的缘故。考虑图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区方格数相等相矛盾,定理证毕。
湘教版九年级上册数学第1章1.2反比例函数的图像与性质答案第2课时学法大视野答案
人教版九年级上册数学第二十一章21.2.1配方法基础训练(2)阳光学业评价答案
湘教版九年级上册数学第2章2.3一元二次方程根的判别式学法大视野答案
湘教版九年级上册数学第1章1.2反比例函数的图像与性质答案第1课时学法大视野答案
湘教版九年级上册数学第1章1.1反比例函数学法大视野答案
湘教版九年级上册数学第4章4.3解直角三角形学法大视野答案
湘教版九年级上册数学第3章3.6位似学法大视野答案
湘教版九年级上册数学第3章3.3相似图形学法大视野答案
北师大版三年级上册数学总复习第6课时乘法长江全能学案答案
湘教版九年级上册数学第2章基础巩固与训练学法大视野答案
北师大版三年级上册数学期末检测题长江全能学案答案
湘教版九年级上册数学第4章4.1正弦和余弦第2课时学法大视野答案
湘教版九年级上册数学第2章2.2.3因式分解法学法大视野答案
湘教版九年级上册数学第3章3.1.1比例的基本性质学法大视野答案
湘教版九年级上册数学第5章5.2统计的简单应用学法大视野答案
湘教版九年级上册数学第2章2.2.1配方法第2课时学法大视野答案
湘教版九年级上册数学第2章2.1一元二次方程学法大视野答案
湘教版九年级上册数学第3章3.5相似三角形的应用学法大视野答案
湘教版九年级上册数学第4章4.4解直角三角形的应用第1课时学法大视野答案
湘教版九年级上册数学第3章3.2平分线分线段成比例学法大视野答案
湘教版九年级上册数学第5章基础巩固与训练学法大视野答案
湘教版九年级上册数学第4章4.4解直角三角形的应用第2课时学法大视野答案
北师大版三年级上册数学总复习练习二十四长江全能学案答案
湘教版九年级上册数学第4章4.1正弦和余弦第1课时学法大视野答案
北师大版三年级上册数学总复习第5课时周长长江全能学案答案
湘教版九年级上册数学第1章基础巩固与训练学法大视野答案
湘教版九年级上册数学第3章基础巩固与训练学法大视野答案
北师大版三年级上册数学总复习第4课时乘与除长江全能学案答案
湘教版九年级上册数学第3章3.4.1相似三角形的判定第1课时学法大视野答案
人教版九年级上册数学第二十一章21.1一元二次方程阳光学业评价答案
小学 |
初中 |
高中 |
不限 |
一年级 | 二年级 |
三年级 | 四年级 |
五年级 | 六年级 |
初一 | 初二 |
初三 | 高一 |
高二 | 高三 |
小考 | 中考 |
高考 |
不限 |
数学教案 |
数学课件 |
数学试题 |
不限 |
人教版 | 苏教版 |
北师版 | 冀教版 |
西师版 | 浙教版 |
青岛版 | 北京版 |
华师大版 | 湘教版 |
鲁教版 | 苏科版 |
沪教版 | 新课标A版 |
新课标B版 | 上海教育版 |
部编版 |
不限 |
上册 |
下册 |
不限 |