发新话题
打印【有0个人次参与评价】

[数学] 2008-12-15 初二

2008-12-15 初二

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

TOP

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

TOP

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

TOP

引用:
原帖由 老猫 于 2008-12-15 07:03 发表 \"\"
有一个10行10列的方格表,在表中任选9个方格涂黑,然后再逐步将凡是与两个或两个以上黑格相邻的方格涂黑,证明:无论怎样选择最初的9个方格,都不能按这样的法则将所有方格全部涂黑。
演变为一般性,设n*n的方格表,证明:无论怎样选择最初的n-1个方格,都不能按这样的法则将所有方格全部涂黑。
找个解答出来了。.

附件

20081215.jpg (294.7 KB)

2008-12-15 19:24

20081215.jpg

TOP

回复 4#ITmeansit 的帖子

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

呵呵.

TOP

回复 5#chin 的帖子

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

TOP

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

TOP

回复 7#老猫 的帖子

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

TOP

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

TOP

回复 9#老猫 的帖子

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

TOP

回复 10#ITmeansit 的帖子

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

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

TOP

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

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

TOP

发新话题