Question

【题目】对方格表中的小方格进行染色．使得每个被染色的小方格满足：与其相邻的小方格中最多只有一个被染色，其中两个小方格相邻是指它们有一条公共边．问：最多可以给多少个小方格染色?

Answer 1

【答案】见解析

【解析】

最多给26个小方格染色．如图的染色满足条件．

下面证明：最多可给26个小方格染色．

首先，由题意可知，对于任何方格表最多将其中的两个小方格染色；对于方格表最多可以将其中的5个小方格染色，使其满足条件．

其次，对于方格表，是在方格表的基础上增加了宽度为2的“镶边”（如图），而镶边最多可以划分成4个的方格表，其中右下角的两个方格中，一个被重复使用，一个没有使用，于是，最多可以增加染色格9个，且增加9个染色格时，必须是右下角的方格被染色，而重复使用的格没有被染色，即的方格表最多被染色14个，且染色14个格时右下角的方格被染色．

最后，方格表是在方格表基础上增加了宽度为2的镶边（如图）．同理，最多可以增加13个染色格，且增加13个染色格时，必须是右下角的方格被染色，而重复使用的格没有被染色，即最多可以染色27个格．此时，不妨设最后一行、倒数第二列的方格未染色（否则，倒数第二行最后一列的方格未染色），则由前面的分析可知，倒数后两行、倒数第三列的两个方格被染色，矛盾．故最多可以染色26个方格．

综上所述，最多给26个小方格染色．