求助,证明在m*n方格中当且仅当m或n奇数时,才存在这种走法:从左上格
发布网友
发布时间：2024-08-18 18:18
共1个回答
热心网友
时间：2024-09-08 00:40
当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
