Question

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

Answer 1

【答案】

【解析】

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

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

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

當(dāng)時(shí)，方格表有7個(gè)格被染色，顯然存在形．

設(shè)當(dāng)時(shí)，結(jié)論成立．

則當(dāng)時(shí)，將方格表左上角拿出方格表．

若其中有個(gè)格被染色，由歸納假設(shè)，其中有形．

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

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

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

故當(dāng)時(shí)，結(jié)論成立．

綜上，最多有個(gè)方格被染色．