| | [屏蔽签名][屏蔽头像]     
[求助]一道题...
今天我去参加了个数学竞赛,有一道题明明看着以前貌似是做过的但现在却非常苦手(3个半小时中有两个半小时都花在这一道题上...),我XXXX(以下省略),好不容易终于自认为做出来了,最后却发现有个条件居然没有用上...(汗!)
总而言之,现在想请某些高人(比如说月无名这样的,虽然最近没怎么见到他了,不过我相信还是有很多高人的!)帮我找找我的方法错在哪里.
题目:
在有无限个方格的"棋盘"中,放置一些长方形(包括正方形).这些长方形的四条边均在格子的边上(翻译的不太好,就是指这些方形的边没有经过空白的地方,全部都在横线或竖线上,原句为「sides run along the grid lines」).并且这些方形没有任何重合的部分,且每个方形均包含奇数个格子.
求证:可以做到用4种颜色将这些方形全部染色,使得没有任何两个颜色相同的方形有交点(由于不能有重叠,因此指得就是边和边有交点).
我的证明如下:
(1) 若有4个长方形两两相互有相交,设这些长方形为A,B,C,D.则B,C,D和A的相交边不可能全部在A的一条边上,因为如果这样的话BC,BD,CD中肯定有不相交的,矛盾了.
(2) 由(1)的结论,并同样用在B,C,D上,可以得知若4个长方形两两相互有交点,所有长方形都至少有两条边与其他的长方形相交.
(3) 若5个长方形两两相互有相交,设其为A,B,C,D,E.则由(2)的结论,由于任意4个都两两有相交,则A,B,C,D至少有两条边与其他的相交.若加入E的话,A,B,C,D,E中必然有一些长方形会有3条边与其他长方形有相交.而这意味着至少有一个长方形有一对对边会同时与其他的相交.而这对对边所相交的两个长方形肯定无法相交了.与"5个长方形两两相互有相交"的命题所矛盾了.因此它为假命题.因此5个长方形不可能两两相互有相交.
我们很明显可以发现当只有一个长方形的时候,只需要一种颜色就够了,4种当然也够了.
我们可以设当n个长方形的时候原命题可以做到.而我们如果新加入一个长方形,它将会和一些其他长方形相交.但是新加的长方形如果和4个不同颜色的长方形都相交的话,这说明了那4个长方形已经两两相交了(否则没有必要用4种颜色),这说明了加上新加的那个,总共有5个长方形两两相交了,这与(3)的结论是矛盾的.所以说新加的长方形至多与3种不同颜色的长方形相交,因此它可以用上第4种颜色.原题的命题仍然能做到.
由数学归纳法,我们可以得出当有无限个长方形时原命题也永远是可以做到的.
-------------------------------------------------------------------------------------------------
目前我有一个条件没有用上:"每个方形均包含奇数个格子"
各位高人能否帮我找找我证明中有什么漏洞,或者举出一个当有一些方形包含偶数个格子时的反例(我当时找了很久都没找出来...)
[ 此贴被古河渚在2008-10-13 05:13重新编辑 ]
| 
叫我"小渚"就好
「即使不能飞,也尽全力去飞」...难道不比「能飞而去飞」要...厉害很多,很多吗?
| | [楼 主] | Posted: 2008-10-13 05:06 | [顶端] | |
您尚未入住！ 现在登录 免费注册 ┋ 搜索 ┋ 社区服务 ┋ 风格选择 ┋ 帮助 
