一道填色问题

jx215

如图，有5X5的矩形框，现在在矩形框里选一些格子涂上颜色，这些涂过颜色的格子将未涂色的格子分开，使得未涂色的格子最多只能有3个格子相邻（包括横，竖和斜线部分）。
问：一，必须在5X5矩形框里最少选多少格子涂上颜色才能达到要求？为什么？（以图中为例，有8个格子填了颜色才满足要求）
二，若是改成6X6矩形框呢？

----------------------------------------------------------------
如图，将一个5×5的网格涂成黄白二色，若要求每一行、每一列和每条长度超过3格的斜线上的连续白格串的长度不超过3格，问至少要求几个黄色格？
-------管理员hujunhua2014年1月4日17：15注。加此注后，跟帖中对主题描述不清的质疑将进行屏蔽或删除。

LZC_314

像五子棋一样，每行或每列或每斜行上面，最多连续的白色格子数不超过个， 这样理解是不是合适点。

jx215

LZC_314 发表于 2014-1-3 11:19
像五子棋一样，每行或每列或每斜行上面，最多连续的白色格子数不超过个， 这样理解是不是合适点。

差不多。即每行每列每斜线行不超过3个

Lwins_G

如图，只需填7格即可。
至于6格不可的证明，大家不妨自己试一试。

wayne

看了第一页还是一头浆糊. 看到了第二页 LZC_314的回帖, 才彻底搞明白了.
说白了, 就是 不存在超过3个同色的格子 "连续共线"呗.

jx215

wayne 发表于 2014-1-3 23:53
看了第一页还是一头浆糊. 看到了第二页 LZC_314的回帖, 才彻底搞明白了.
说白了, 就是 不存在超过3个同色 ...

是这样的。

现在13F已经给出了最少7格，只要证明了6格达不到要求就行了

hujunhua

要证明6格不够，篇幅还不算太长。用反证法，假定有一个合适的6格方案图G。

在图G中，行和列包含的黄格数分布都是｛1,1,1,1,2}(不管顺序）,
其中，黄格数为1的行，所含的唯一黄格必定位于列3,4,5. 所以黄格数为2的列必为列3,4 or 5
同样，黄格数为1的列，所含的唯一黄格必定位于行3,4,5. 所以荶格数为2的行必为行3,4 or 5
于是初步可得图1所示的结果：网格的4角必为白格，4边的中间带，即图中的4个灰色带各含一个黄格，剩下的2个黄格在中心九宫格待涂.

图1

图1

列1与列5的黄格必定同行，否则，行3,4,5就会都包含4连白格（暂时），都需要待涂的黄格来分割，但只有2个待涂黄格了。
同理，行1与行5的黄格同列。
所以，将图1的灰幕揭开后，可能的图案有9种，合并那些对称重复的，不重复的有3种，如图2, 图3, 图4 。

图2

图3

图4

在图2,3, 4 中，剩下待涂的两黄格位于灰色格内，无论如何都有斜线含连4白格。所以假设不成立，6格不够。