Question

【題目】對方格表中的小方格進行染色．使得每個被染色的小方格滿足：與其相鄰的小方格中最多只有一個被染色，其中兩個小方格相鄰是指它們有一條公共邊．問：最多可以給多少個小方格染色?

Answer 1

【答案】見解析

【解析】

最多給26個小方格染色．如圖的染色滿足條件．

下面證明：最多可給26個小方格染色．

首先，由題意可知，對于任何方格表最多將其中的兩個小方格染色；對于方格表最多可以將其中的5個小方格染色，使其滿足條件．

其次，對于方格表，是在方格表的基礎上增加了寬度為2的“鑲邊”（如圖），而鑲邊最多可以劃分成4個的方格表，其中右下角的兩個方格中，一個被重復使用，一個沒有使用，于是，最多可以增加染色格9個，且增加9個染色格時，必須是右下角的方格被染色，而重復使用的格沒有被染色，即的方格表最多被染色14個，且染色14個格時右下角的方格被染色．

最后，方格表是在方格表基礎上增加了寬度為2的鑲邊（如圖）．同理，最多可以增加13個染色格，且增加13個染色格時，必須是右下角的方格被染色，而重復使用的格沒有被染色，即最多可以染色27個格．此時，不妨設最后一行、倒數第二列的方格未染色（否則，倒數第二行最后一列的方格未染色），則由前面的分析可知，倒數后兩行、倒數第三列的兩個方格被染色，矛盾．故最多可以染色26個方格．

綜上所述，最多給26個小方格染色．