地图着色.docVIP

地图着色 　　同学们对地图是很熟悉的，但你是否注意到地图中各国或者各省的颜色数目？ 　　185213年，直至逝世仍毫无结果。 　　1876年，当时很有名望的数学家凯莱在数学年会上把这个问题归纳为“四色猜想”提出，并征求问题的解答。于是“四色猜想”开始引人注目。 　　(讲不下去了)。但他仍胸有成竹，确信可证明此问题。可是一连几个星期的课，他都以失败而告终。有一天，他疲惫不堪地走进教室，当时正值惊雷震耳，暴雨滂沱，他十分愧疚地对同学说：“唉，看来上帝也在责怪我的狂妄自大！四色猜想真难呀，我简直拿他毫无办法。” 　　1890年希伍德首先解决了“五色问题”。科学家们此后的进展是：1922年证明了一张地图国家不超过25个时，定理成立，1938年证明了地图国家数为32个，1940年又提高到35个，1969年提高到39个。进展速度如此之慢，可见问题的难度。 　　1972年，这条道路仍然未打通。 　　1972年，美国的数学家阿沛尔和哈肯，沿用原来证明的基本思想设计出一个计算程序，他们同时启动三台超高速电子计算机，经过1200小时的计算，终于在1975年9月获得“四色定理”的证明。这是世界上最长的证明。现在回忆起来，这个难题却是一个不起眼的小人物提出来的。所以，著名科学家李政道在给中国科技大学少年班学员讲课时说：“最重要的是会提出问题，否则将来就做不了第一流的工作。”这是多么正确啊！ 　　由“四色定理”开始，人们还引出了许多其他有趣的染色问题，我们来看下面一些例子。 　　1 用红、蓝、黄三种颜色给正四面锥体染色，问至多可以涂出多少种不同的锥体？ 　　解：我们先来看用红、蓝两色涂色的情况： 　　2个。 　　2个。 　　1个。 　　5个不同的锥体。 　　如果用三种颜色，我们作以下分类： 　　3个。 　　6个。 　　3个。 　　3个。 　　3＋6＋3＋3=15个。 　　36个，75个。 　　2 用m块凸字形红色瓷砖和n块2×1形绿色瓷砖恰好铺满一个6×5的长方形地面(如图(1)与(2))．这时n的最小值必定是3．你能说明理由吗？ 　　解：这是要说理的问题，我们分步考虑： 　　6块红砖3块绿砖的铺地方法呢？你试一试，容易找出。如图(2)就是一种铺法。 　　n＜3时无法铺成。 　　m块凸形砖和n块2×1形砖。则它们占的方格数有等式 4m＋2n=6×5，即 2m＋n=15． 　　 　　n≠1，即不能用1块2×1形砖7块凸形砖把地铺好。 　　1块2×1型砖铺，必然盖住一黑一白。用凸形砖铺，盖住三黑一白或者三白一黑。设有x块凸形砖盖住三黑一白，则有7-x块凸形砖盖住三白一黑。总共盖住黑方格数为3x＋(7-x)＋1． 　　15个，所以有方程 　　 　　2×1型的绿砖至少要用3块。 　　3 如图(3)将正方形ABCD分割成n2个相等的小方格(n为正整数)，把相对顶点A，C染成红色，B，D染成蓝色，其它各交点染成红、蓝中的任一色，把各小方格四个顶点都染上色后，你能证明其中有三个顶点颜色相同的小方格数必为偶数吗？ 　　1，蓝色为-1．如果小方格四顶点有三个顶点同色，另一顶点不同色，则此四个数的乘积应该是-1．如果小方格四顶点同色或者两两顶点分别同色，那么此四个数乘积为1． 　　k个小正方形四顶点中有三顶点同色，则所有n2个小正方格顶点的数的乘积为 1×(-1)k=(-1)k． 　　(-1)k=1，就证明了k为偶数。为此，我们来考虑这些顶点在组成各小正方形时所表示的数共用了多少次。这里有三种类型： 　　A，B，C，D，各用了一次。乘积为1×(-1)×1×(-1)=1． 　　 AB，BC，CD，DA上除了 A，B，C，D四顶点外的点。由于相邻两正方形各用了一次，所以每个点用了两次。它们所表示的数的乘积显然为1． 　　4次，它们所表示的数的乘积也必然是1． 　　1，即(-1)k=1，所以k为偶数。