旺旺网 - Powered by Discuz! Board

标题: [数学] 2008-12-15 初二 [打印本页]

作者: 老猫 时间: 2008-12-15 07:03 标题: 2008-12-15 初二

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

作者: chin 时间: 2008-12-15 18:38

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

作者: chin 时间: 2008-12-15 18:40

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

作者: ITmeansit 时间: 2008-12-15 19:24

引用:

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

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

作者: chin 时间: 2008-12-15 19:47 标题: 回复 4#ITmeansit 的帖子

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

呵呵.

作者: ITmeansit 时间: 2008-12-15 20:05 标题: 回复 5#chin 的帖子

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

作者: 老猫 时间: 2008-12-15 21:05

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

作者: ITmeansit 时间: 2008-12-15 21:24 标题: 回复 7#老猫的帖子

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

作者: 老猫 时间: 2008-12-15 21:30

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

作者: ITmeansit 时间: 2008-12-15 21:36 标题: 回复 9#老猫的帖子

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

作者: 老猫 时间: 2008-12-15 21:49 标题: 回复 10#ITmeansit 的帖子

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

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

作者: chin 时间: 2008-12-16 08:40

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

这种显然的东西是最不容易证明的。

记得猫老师说过，属于就地打滚。

欢迎光临旺旺网 (http://ww123.net/)