杂题之染色问题练习4

小学教育网

　　在平面上有一个27×27的方格棋盘，在棋盘的正中间摆好81枚棋子，他们被摆成一个9×9的正方形。按下面的规则进行游戏：每一枚棋子都可沿水平方向或竖直方向越过相邻的棋子，放进紧挨这枚棋子的空格中，并把越过的这个棋子取出来。问：是否存在一种走法，是棋盘最后恰好剩下一枚棋子？
　　分析解答：
　　分析游戏规则“每一枚棋子都可沿水平方向或竖直方向越过相邻的棋子，放进紧挨着这枚棋子的空格中，并把越过的这格棋子取出来”，可知：每走一步，走动棋子格、与它相邻被取出的棋子格、落子的空格，这三个格内棋子的状态，有或无，同时发生变化。因此可将整个棋盘按水平和竖直方向用三种颜色染色，开始时，
　　“棋盘的正中间摆好81枚棋子,它们被摆成一个9×9的正方形”，知三种颜色格子中棋子数是相同的（9×9/3=27），棋子数的奇偶性相同。由于每走一步，三种颜色格子里棋子数的奇偶性同时改变，因此三种颜色棋子数的奇偶性始终相同.
　　要使“棋盘上最后恰好剩下一枚棋子”，三种颜色的格子里棋子数2种颜色为0，1种颜色为1，两偶一奇，按上述走法显然是不可能的。
　　所以，不存在这样一种走法，使棋盘上最后恰好剩下一枚棋子。