國際象棋中的數學證明問題
來源:網絡 2009-09-11 09:42:53

一個國際象棋盤,是一個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區方格數相等相矛盾,定理證畢。
相關文章
- 小學1-6年級作文素材大全
- 全國小學升初中語數英三科試題匯總
- 小學1-6年級數學天天練
- 小學1-6年級奧數類型例題講解整理匯總
- 小學1-6年級奧數練習題整理匯總
- 小學1-6年級奧數知識點匯總
- 小學1-6年級語數英教案匯總
- 小學語數英試題資料大全
- 小學1-6年級語數英期末試題整理匯總
- 小學1-6年級語數英期中試題整理匯總
- 小學1-6年語數英單元試題整理匯總