有一个10行10列的方格表，在表中任选9个方格涂黑，然后再逐步将凡是与两个或两个以上黑格相邻的方格涂黑，证明：无论怎样选择最初的9个方格，都不能按这样的法则将所有方格全部涂黑。.

考虑涂黑过程中黑色区域的周界总长度。
设小方格的边长为1，则开始有9个黑格，黑色区域总长度不大于4x9=36。
按照题设的涂黑法则，每格在涂黑前后，黑色区域的周界不会变长。
因为此方格至少有两边是原来黑色区域的周界，当此格涂黑后，这两边已不再是边界，而另两边可能成为边界。
如果能将所有方格都涂黑，那么黑色边界的总长度应为4x10=40.
由以上分析，40>36，这是不可能的。
因此，无论怎样选择最初的9个方格，都不可能按照题设的法则将全部方格涂黑。.

事实上10个方格涂黑就可以了
构造法——对角线方格涂黑.

引用:

原帖由 老猫 于 2008-12-15 07:03 发表
有一个10行10列的方格表，在表中任选9个方格涂黑，然后再逐步将凡是与两个或两个以上黑格相邻的方格涂黑，证明：无论怎样选择最初的9个方格，都不能按这样的法则将所有方格全部涂黑。

演变为一般性，设n*n的方格表，证明：无论怎样选择最初的n-1个方格，都不能按这样的法则将所有方格全部涂黑。
找个解答出来了。.

首先要证明
当n个方格对角线方式选定时，可染色达到最大nxn

呵呵.

手画一下即可了，呵呵。比较简单。.

应该认为2楼的证法较好。
应该认为4楼的字非常漂亮。但是解法有漏洞。漏洞在五楼已经被指出了。.

我当时按照题解手画了一次，认为没有五楼指出的漏洞啊。
沿对角线选定黑格，首先余对角线“左右相邻”的各n-1个方格被涂黑，再次是各n-2个方格被涂黑，。。。。一直到n*n方格全部被涂黑。.

问题就是为什么一定是最多的。.

n*n全部被涂黑，为什么还不是最多呢？.

这个理由是如果在n*n的格子里面，最多能画到满。
没有错。

但是在更大的格子里面，为什么就最多只能画到这么多，就可疑了。.

n*n全部被涂黑，为什么还不是最多呢？

这种显然的东西是最不容易证明的。
记得猫老师说过，属于就地打滚。.