Question

【題目】將的方格表中的某些小方格染黑，使得不存在由三個黑色小方格構成的形（共四種情形）．求最多有多少個小方格被染色？

Answer 1

【答案】

【解析】

用歸納法證明：方格表最多有個方格被染色．

首先，將第一行和第三行，最后一行染色．顯然滿足條件，且被染色格數目為．

其次證明：若有個格被染色，則存在形．

當時，方格表有7個格被染色，顯然存在形．

設當時，結論成立．

則當時，將方格表左上角拿出方格表．

若其中有個格被染色，由歸納假設，其中有形．

若其中有至多格被染色，則剩下大形的兩行兩列中共有至少格被染色．

將大形豎直方向拿出行，至多有個格被染色才沒有形．

同理，橫方向行至多有個格被染色．但只有右下角一格未處理，即使其被染色，還有一個染色格．無論其在何處，必有形．

故當時，結論成立．

綜上，最多有個方格被染色．