Question

【題目】計算機屏幕上顯示了一個98×98的棋盤，將棋盤用通常方法染色(即兩種顏色相間地染)。一個人能夠拖動鼠標(biāo)選擇一個邊框為棋盤線的矩形，然后點擊鼠標(biāo)，這個框內(nèi)所有的顏色變色(即白變黑、黑變白)。問至少要點擊多少次鼠標(biāo)才能將整個棋盤變成同一種顏色?證明你的結(jié)論。

Answer 1

【答案】98

【解析】

我們證明對n×n的棋盤，如果n為奇數(shù)，則至少需要點擊n-1次鼠標(biāo)，才能將整個棋盤變成同一種顏色；如果n為偶數(shù)，則至少需要點擊n次鼠標(biāo)，才能將整個棋盤變成同一種顏色.

考慮沿著邊框線的4(n-1)個小方格，由于它們黑白相間，故一共有4( n-1)對由相鄰異色小方格組成的異色小方格對.而每一次點擊至多減少4對這樣的異色小方格對，故至少要點擊n-1次鼠標(biāo)，才能將整個棋盤變成同一種顏色.

(1) n為奇數(shù).

i 若n=1，則棋盤只有一種顏色，無需點擊鼠標(biāo)；

ii 若n=2k+1(k為正整數(shù))，則可先點擊第2,4,...，2k行，再點擊第2,4,...，2k列(每次點擊可減少4對異色小方格對)，共點擊n-1次鼠標(biāo)即可將整個棋盤變成同一種顏色.

(2) n為偶數(shù).

設(shè)n=2k(k為正整數(shù))，由于這個棋盤的四個頂點不同色，故必有矩形包含這些頂點.而點擊這些矩形一次至多可以減少2對異色小方格對，所以，至少需要點擊n次鼠標(biāo)，才能將整個棋盤變成同一種顏色----可先點擊第2,4,...，2k行，再點擊第2，4,...,2k列，第k次和第2k次點擊鼠標(biāo)每次可減少2對異色小方格對，其余各次點擊鼠標(biāo)每次可減少4對異色小方格對，共點擊n次.

因此，至少要點擊98次鼠標(biāo)，才能將一個98×98的棋盤變成同一種顏色.