无穷地图的四色问题

fzy · 发表于 2005-9-15 23:30:46

难度：++

对平面上有限多个国家的地图进行染色，4种颜色就够了。现在假设平面上有无穷多个国家G1，G2，G3，。。。，每个国家可能和无穷多个其他国家接壤。4种颜色还够不够？

Jenny · 发表于 2005-9-16 01:42:34

够了

QL · 发表于 2005-9-16 04:52:42

Let's denote H4 ={G1, G2, G3, G4}; H5={G1,G2,..,G5}.....

Obviously a soultion to H5, confined on H4 will also be a solution of H4. We can also say that this restricted solution on H4 can be 'extended' to H5.

We can show the following:

(1)if a solution of H4 can be extended to Hm (m>=5) then it can be extended to H5,H6,...Hm

(2)There is at least one solution of H4 that can be extended to any Hm (m>4), let's pick one of such a solution, S4=(C1,C2,C3,C4), where the Ci's are the colors for each country of H4.

Now, move to H5, by similar argument we can prove that, we can pick a color C5, so that S5=(C1,C2,C3,C4,C5) can be extened to H6,H7, .....

and so on.....

fzy · 发表于 2005-9-16 19:25:03

Care to tell us why, 观音姐姐? (Why did he call you 观音姐姐? )

fzy · 发表于 2005-9-16 19:25:59

Idea right, statement can be simpler.

Jenny · 发表于 2005-9-16 19:30:02

我也不知为什么，可能是我冤枉了他吧。

		自动登录	找回密码
密码			立即注册

动态微博

无穷地图的四色问题

回复：无穷地图的四色问题

回复：无穷地图的四色问题

回复：回复：无穷地图的四色问题

Idea right, statement can be simpler.

回复：回复：回复：无穷地图的四色问题

浏览过的版块