<th id="spi40"><option id="spi40"></option></th>

    <thead id="spi40"><sup id="spi40"></sup></thead>
    1. <object id="spi40"></object>
      1. 趣題妙解──國際象棋中的問題

        查看: 日期:2015-09-21 【字體:
        一個國際象棋盤。是一個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均尚未跳過。有以下情形: 

         ?。╥)(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區的跳躍。 

         ?。╥i)(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區方格數相等相矛盾,定理證畢。
        專題
        在線客服
        可提现的游戏