打印【有0个人次参与评价】

[数学] 2008-12-15 初二

1楼老猫

老猫 (谦虚使人进步，骄傲使人快乐。) 发表于 2008-12-15 07:03 只看此人

2008-12-15 初二

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

TOP

2楼chin chin (08，09) 发表于 2008-12-15 18:38 只看此人

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

TOP

3楼chin chin (08，09) 发表于 2008-12-15 18:40 只看此人

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

TOP

4楼ITmeansit ITmeansit (......) 发表于 2008-12-15 19:24 只看此人

引用:

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

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

附件

20081215.jpg (294.7 KB)

2008-12-15 19:24

TOP

5楼chin chin (08，09) 发表于 2008-12-15 19:47 只看此人

回复 4#ITmeansit 的帖子

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

呵呵.

TOP

6楼ITmeansit ITmeansit (......) 发表于 2008-12-15 20:05 只看此人

回复 5#chin 的帖子

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

TOP

7楼老猫

老猫 (谦虚使人进步，骄傲使人快乐。) 发表于 2008-12-15 21:05 只看此人

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

TOP

8楼ITmeansit ITmeansit (......) 发表于 2008-12-15 21:24 只看此人

回复 7#老猫的帖子

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

TOP

9楼老猫

老猫 (谦虚使人进步，骄傲使人快乐。) 发表于 2008-12-15 21:30 只看此人

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

TOP

10楼ITmeansit ITmeansit (......) 发表于 2008-12-15 21:36 只看此人

回复 9#老猫的帖子

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

TOP

11楼老猫

老猫 (谦虚使人进步，骄傲使人快乐。) 发表于 2008-12-15 21:49 只看此人

回复 10#ITmeansit 的帖子

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

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

TOP

12楼chin chin (08，09) 发表于 2008-12-16 08:40 只看此人

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

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

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

.

TOP

[数学] 2008-12-15 初二

2008-12-15 初二

引用:

附件

回复 4#ITmeansit 的帖子

回复 5#chin 的帖子

回复 7#老猫 的帖子

回复 9#老猫 的帖子

回复 10#ITmeansit 的帖子

回复 7#老猫的帖子

回复 9#老猫的帖子