求助，证明在m*n方格中当且仅当m或n奇数时，才存在这种走法：从左上格

Question

求助，证明在m*n方格中当且仅当m或n奇数时，才存在这种走法：从左上格出发经过所有方格一次最终到达右下角方格

Answer 1

充分性：
当m是奇数时
m=1时显然
m>1时先走完第一行（左->右），然后走完第二行（右->左），再用归纳假设。
当n是奇数时可以按列走

必要性：
若m和n都是偶数，对所有的格子进行0-1编号，使得任何相邻（存在公共边）的两格的编号都相反。这样每走一格都会改变编号。注意一共要走奇数步，所以出发点和终点的编号相反，但左上角和右下角的编号相同（用归纳法容易证明），矛盾。

如果不明白的话看这个例子
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0