一道题请大家踊跃参加尝试

lzk05_lzk0530

在9×9的方格表中取出46
个方格染成红色．证明：存在一块由4个方格
构成的2×2区域，其中有至少3个方格被染
成红色

战巡

呵呵..........这个嘛~~~
首先可以通过穷举的办法(或者其他什么办法)证明一个3*3的格子里,要满足任意2*2区域内没有3个或以上都被染色的条件,最多只能有5个格子被染色,那么9*9的区域可以分成9个3*3区域,那么完全按照最大值算,就是说不管两个3*3区域的重叠部分可能不满足条件的那些,都只有45个被染色的格子,再加1个,就无论如何都不可能满足条件了

lzk05_lzk0530

首先，考察9×2的方格表．
如图7，设第1行有x1个方格被染成红色，第2
行有x2个方格被染成红色．
下面证明：若x1+x2 ≥11，则必存在一块由4个
方格构成的2×2区域，其中有至少3个方格被染成
红色；若x1+x2 =10，则只有唯一的情形(如图8)能
够使得不存在由4个方格构成的2×2区域，其中至
少3个方格被染成红色．
将9×2方格表从左向右分成4个2×2方格和
一个1×2区域．若不存在至少3个方格被染成红色
的2×2区域，则前4个2×2方格中的每个中至多
有两个方格被染成红色．于是，总的红色方格数不超
过4×2+2=10<1l，矛盾．
故当x1+x2≥11时，结论成立．
当x1+x2 =10时，必存在某一列中的ai和bi
同时被染成红色．为保证不存在2×2区域中有至少
3个方格被染成红色，则要求a（i-1）和b （i-1），a（i+1）和
b（i+1） 不被染成红色，显然，只有图8的情形满足．
再回到本题．
假设存在某种染色方案使得9×9方格表中不
存在有至少3个方格被染成红色的2×2区域．
若该方案中存在相邻的两行(第k行和第k+1
行)满足xk+x（k+1）=10，则必有xk=x（k+1）=5．若k为
奇数，则沿第k行将方格表分成上、下两部分，上面
有偶数行，下面也有偶数行，由前面的结论知，剩下
的8行中至多有4×10=40个方格被染成红色．于
是，总的红色方格数不超过40+5=45．若k为偶数，
则沿第k+1行划分，有相同的结论．
若任意相邻两行的红色方格数之和均不等于
10。则
( x1+ x2)+(x 3+x 4)+(x 5+ x6)+(x 7+x 8)+x 9
≤4×9+9=45．
因此，无论如何染色，要使9×9方格表中不存
在有至少3个方格被染成红色的2×2区域，最多只
能有45个方格被染成红色，与题设矛盾．
综上所述，必存在一块由4个方格构成的2×2
区域，其中有至少3个方格被染成红色．

[ 本帖最后由 lzk05_lzk0530 于 2008-4-5 10:45 编辑 ]