Question

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

Answer 1

【答案】98

【解析】

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

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

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

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

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

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

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

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