Question

【题目】将的方格表中的某些小方格染黑，使得不存在由三个黑色小方格构成的形（共四种情形）．求最多有多少个小方格被染色？

Answer 1

【答案】

【解析】

用归纳法证明：方格表最多有个方格被染色．

首先，将第一行和第三行，最后一行染色．显然满足条件，且被染色格数目为．

其次证明：若有个格被染色，则存在形．

当时，方格表有7个格被染色，显然存在形．

设当时，结论成立．

则当时，将方格表左上角拿出方格表．

若其中有个格被染色，由归纳假设，其中有形．

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

将大形竖直方向拿出行，至多有个格被染色才没有形．

同理，横方向行至多有个格被染色．但只有右下角一格未处理，即使其被染色，还有一个染色格．无论其在何处，必有形．

故当时，结论成立．

综上，最多有个方格被染色．