Question

【題目】將一枚棋子放在一個的棋盤上，記為從左、上數第行第列的小方格，求所有的四元數組，使得從出發，經過每個小方格恰一次到達（每步為將棋子從一個小方格移到與之有共同邊的另一個小方格）.

Answer 1

【答案】所求為，且當為偶數時，；當為奇數時，.

【解析】

將棋盤按國際象棋方式黑邊相間染色，其中，為黑色，

當為奇數時，任兩個黑色的小方格滿足條件，當為偶數時，任兩個異色的小方格滿足條件.

記以下結論為.

下面用數學歸納法證明，

先證下面的引理.

引理1 與等價

顯然成立.

引理2 在棋盤中，不同列的異色的兩個小方格滿足條件.

引理2的證明：若同行，因二者異色，則其中間有偶數列，由如圖方式知滿足條件.

若不同行，因二者異色，則其中間有奇數列，由如圖方式知滿足條件.

引理3 若成立，則成立，

引理3的證明：對棋盤，分兩種情況討論：

（1）若都不在前（后）兩列，則在后（前）面的棋盤中，有成立，且在前（后）第三列中必有相鄰方格是中棋子走過的路徑中連續的兩個方格（設為）,可用如圖

方式將前（后）兩列并入棋子原來的路徑，使成立.

（2）若一個在前兩列，另一個在后兩列，不妨設在前兩列，則在第二列有至少兩個方格與異色，其中至少有一個方格（記為）與不同行，由引理知在前棋盤中，滿足條件，取第三列中與相鄰的方格（與同色），則由成立，知在后棋盤中，滿足條件.

故由,使成立.

由（1）、（2）知成立.

類似可證：

引理4 若成立，則成立.

回到原題

由引理知，為利用數學歸納法，只需證明成立即可.

對異色.

若相鄰，則由如圖

環路知滿足條件.

若不相鄰，當都在上（下）兩行時，由引理2知在棋盤中，滿足條件.

類似引理3

（1）知有的路徑使成立，當一個在上兩行，另一個在下兩行時，類似引理3（2）知有

的路徑使成立.

對，同黑.

先由圖知成立.

再分兩種情況證成立.

若都在前（后）三列，則由成立，知在前（后）棋盤中，滿足條件，類似引理3（1）知在棋盤中有路徑使成立.

若一個在前兩列，另一個在后兩列，不妨設在前兩列，由引理2知，在第2列中存在白方格,在第4列中存在白方格，使得分別在前、后棋盤中，、分別滿足條件，如圖

方式將、相連，則使成立.

最后分兩種情況證成立.

若都在前（后）三列，則由成立，類似引理可知在棋盤中，有路徑使成立.

若一個在前兩列，另一個在后兩列，類似中第2種情況知在棋盤中有路徑使成立.

故成立.

綜上，所求為，且當為偶數時，；

當為奇數時，.