Question

【題目】將n×n的棋盤的部分結(jié)點(diǎn)(單位正方形的頂點(diǎn))染紅，使得任意一個(gè)由單位正方形構(gòu)成的k×k的子棋盤的邊界上至少有一個(gè)紅點(diǎn)．記滿足條件的紅點(diǎn)數(shù)的最小值為. 試求的值.

Answer 1

【答案】

【解析】

對(duì)任意一個(gè)紅點(diǎn)P進(jìn)行賦值，若包含P的某個(gè)單位正方形的邊界上有m個(gè)紅點(diǎn)，則P從該單位正方形處得到的“分?jǐn)?shù)”.將點(diǎn)P從包含它的所有單位正方形處得到的分?jǐn)?shù)相加，就得到點(diǎn)P處的值.

對(duì)在棋盤的邊界上的紅點(diǎn)，每個(gè)點(diǎn)處的值至多為2．而對(duì)于在棋盤內(nèi)部的某個(gè)紅點(diǎn)P，考察以P為中心的2×2的子棋盤，它的邊界上至少還有一個(gè)紅點(diǎn)Q．對(duì)于同時(shí)包含P和Q的單位正方形，P從中得到的分?jǐn)?shù)至多為，于是，點(diǎn)P的值至多為

這表明，任一個(gè)紅點(diǎn)處的值至多為 則個(gè)紅點(diǎn)處的值的總和至多為

而由賦值的方法可知，棋盤中每個(gè)紅點(diǎn)處的值的總和應(yīng)為

從而，，即

考察如下的棋盤，這里，

對(duì)這個(gè)的左上角的7×7子棋盤按圖4所示進(jìn)行染色.

將其染色方法擴(kuò)展到整個(gè)的棋盤，則任何k×k的子棋盤的邊界上至少有一個(gè)紅點(diǎn)．在這種染色方法中，共將個(gè)頂點(diǎn)染為紅色.

考慮該的棋盤的任意一個(gè)n×n的子棋盤，有，

即 ②

結(jié)合式①、②得