题目内容

【题目】n×n的棋盘的部分结点(单位正方形的顶点)染红,使得任意一个由单位正方形构成的k×k的子棋盘的边界上至少有一个红点.记满足条件的红点数的最小值为. 试求的值.

【答案】

【解析】

对任意一个红点P进行赋值,若包含P的某个单位正方形的边界上有m个红点,则P从该单位正方形处得到的“分数”.将点P从包含它的所有单位正方形处得到的分数相加,就得到点P处的值.

对在棋盘的边界上的红点,每个点处的值至多为2.而对于在棋盘内部的某个红点P,考察以P为中心的2×2的子棋盘,它的边界上至少还有一个红点Q.对于同时包含P和Q的单位正方形,P从中得到的分数至多为,于是,点P的值至多为

这表明,任一个红点处的值至多为个红点处的值的总和至多为

而由赋值的方法可知,棋盘中每个红点处的值的总和应为

从而,,即

考察如下的棋盘,这里

对这个的左上角的7×7子棋盘按图4所示进行染色.

将其染色方法扩展到整个的棋盘,则任何k×k的子棋盘的边界上至少有一个红点.在这种染色方法中,共将个顶点染为红色.

考虑该的棋盘的任意一个n×n的子棋盘,有

结合式①、②得

练习册系列答案
相关题目

违法和不良信息举报电话:027-86699610 举报邮箱:58377363@163.com

精英家教网