Question

【题目】将一枚棋子放在一个的棋盘上，记为从左、上数第行第列的小方格，求所有的四元数组，使得从出发，经过每个小方格恰一次到达（每步为将棋子从一个小方格移到与之有共同边的另一个小方格）.

Answer 1

【答案】所求为，且当为偶数时，；当为奇数时，.

【解析】

将棋盘按国际象棋方式黑边相间染色，其中，为黑色，

当为奇数时，任两个黑色的小方格满足条件，当为偶数时，任两个异色的小方格满足条件.

记以下结论为.

下面用数学归纳法证明，

先证下面的引理.

引理1 与等价

显然成立.

引理2 在棋盘中，不同列的异色的两个小方格满足条件.

引理2的证明：若同行，因二者异色，则其中间有偶数列，由如图方式知满足条件.

若不同行，因二者异色，则其中间有奇数列，由如图方式知满足条件.

引理3 若成立，则成立，

引理3的证明：对棋盘，分两种情况讨论：

（1）若都不在前（后）两列，则在后（前）面的棋盘中，有成立，且在前（后）第三列中必有相邻方格是中棋子走过的路径中连续的两个方格（设为）,可用如图

方式将前（后）两列并入棋子原来的路径，使成立.

（2）若一个在前两列，另一个在后两列，不妨设在前两列，则在第二列有至少两个方格与异色，其中至少有一个方格（记为）与不同行，由引理知在前棋盘中，满足条件，取第三列中与相邻的方格（与同色），则由成立，知在后棋盘中，满足条件.

故由,使成立.

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

类似可证：

引理4 若成立，则成立.

回到原题

由引理知，为利用数学归纳法，只需证明成立即可.

对异色.

若相邻，则由如图

环路知满足条件.

若不相邻，当都在上（下）两行时，由引理2知在棋盘中，满足条件.

类似引理3

（1）知有的路径使成立，当一个在上两行，另一个在下两行时，类似引理3（2）知有

的路径使成立.

对，同黑.

先由图知成立.

再分两种情况证成立.

若都在前（后）三列，则由成立，知在前（后）棋盘中，满足条件，类似引理3（1）知在棋盘中有路径使成立.

若一个在前两列，另一个在后两列，不妨设在前两列，由引理2知，在第2列中存在白方格,在第4列中存在白方格，使得分别在前、后棋盘中，、分别满足条件，如图

方式将、相连，则使成立.

最后分两种情况证成立.

若都在前（后）三列，则由成立，类似引理可知在棋盘中，有路径使成立.

若一个在前两列，另一个在后两列，类似中第2种情况知在棋盘中有路径使成立.

故成立.

综上，所求为，且当为偶数时，；

当为奇数时，.