Question

设n和m为任意正整数，有只棋子叫（n，m）鳄鱼，每步横行n格然后直行m格，或直行n格然后横行m格．求证在无限大的方格棋盘上，可用黑白两色涂在方格上，使这棋子每步不是从白格走到黑格，就是从黑格走到白格．

Answer 1

分析：设（n，m）=d，n=ad，m=bd，（a，b）=1，先将棋盘分割成d×d块，每块中的d²个方格彼此同色，再以各块的中心为格点，d为边长作格点阵（每个格点代表d×d块），然后对a，b的奇偶进行分类讨论，最后根据奇偶的特性得到起点和终点有不同色．

解答：证明：设（n，m）=d，n=ad，m=bd，（a，b）=1，
先将棋盘分割成d×d块，每块中的d²个方格彼此同色，再以各块的中心为格点，d为边长作格点阵（每个格点代表d×d块），
（1）若a，b为一奇一偶，依国际象棋盘方式间隔染色，
即当x+y为偶数时将（x，y）染黑色，而x+y为奇数时，将（x，y）染白色，由于a+b为奇数．
故（n，m）每步的起点（x，y）与终点（x±a，y±b）或（x±b，y±a）的坐标和不同奇偶，从而不同色．
（2）若a，b同为奇数，依x的奇偶间隔染色（同一x的整个竖直条同色），
同样因为每步x与x±a或y±b不同奇偶，从而起点与终点不同色，
故在无限大的方格棋盘上，可用黑白两色涂在方格上，使这棋子每步不是从白格走到黑格，就是从黑格走到白格．

点评：本题主要考查染色问题的知识点，证明本题的关键是对a，b进行奇偶数分类讨论，此题的难度较大，特别是熟练掌握染色的原理．