Question

【题目】计算机屏幕上显示了一个98×98的棋盘，将棋盘用通常方法染色(即两种颜色相间地染)。一个人能够拖动鼠标选择一个边框为棋盘线的矩形，然后点击鼠标，这个框内所有的颜色变色(即白变黑、黑变白)。问至少要点击多少次鼠标才能将整个棋盘变成同一种颜色?证明你的结论。

Answer 1

【答案】98

【解析】

我们证明对n×n的棋盘，如果n为奇数，则至少需要点击n-1次鼠标，才能将整个棋盘变成同一种颜色；如果n为偶数，则至少需要点击n次鼠标，才能将整个棋盘变成同一种颜色.

考虑沿着边框线的4(n-1)个小方格，由于它们黑白相间，故一共有4( n-1)对由相邻异色小方格组成的异色小方格对.而每一次点击至多减少4对这样的异色小方格对，故至少要点击n-1次鼠标，才能将整个棋盘变成同一种颜色.

(1) n为奇数.

i 若n=1，则棋盘只有一种颜色，无需点击鼠标；

ii 若n=2k+1(k为正整数)，则可先点击第2,4,...，2k行，再点击第2,4,...，2k列(每次点击可减少4对异色小方格对)，共点击n-1次鼠标即可将整个棋盘变成同一种颜色.

(2) n为偶数.

设n=2k(k为正整数)，由于这个棋盘的四个顶点不同色，故必有矩形包含这些顶点.而点击这些矩形一次至多可以减少2对异色小方格对，所以，至少需要点击n次鼠标，才能将整个棋盘变成同一种颜色----可先点击第2,4,...，2k行，再点击第2，4,...,2k列，第k次和第2k次点击鼠标每次可减少2对异色小方格对，其余各次点击鼠标每次可减少4对异色小方格对，共点击n次.

因此，至少要点击98次鼠标，才能将一个98×98的棋盘变成同一种颜色.