地图着色发现与数学解决的五色问题

同学们对地图是很熟悉的，但你是否注意到地图中各国或者各省的颜色数目?

1852年，刚从伦敦大学毕业的弗南西斯·葛斯里在对英国地图着色时发现，对无论多么复杂的地图，只需用四种颜色就足够将相邻的区域分开。这个千万人屡见不鲜的有趣事实引起了他的注意，他感到这种现象绝非偶然，可能隐藏着深刻的科学道理。他把他的想法告诉了他的哥哥弗德雷克。弗德雷克是著名数学家德·摩根的学生，他对这个问题极感兴趣，凭他的数学敏锐性，他感到这是个数学问题，于是便设法证明。可是，尽管他绞尽脑汁，仍百思不得其解，于是他以“四色定理”为名，请他的老师德·摩根证明。德·摩根写信请著名数学家哈密尔顿帮助解答，这位智慧超群的人也被这个简单的问题弄得一筹莫展，他冥思苦想了13年，直至逝世仍毫无结果。

在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。你能说明理由吗?

解:　这是要说理的问题，我们分步考虑：(www.xing528.com)

图(1)

图(2)

第一步：能不能找到用6块红砖3块绿砖的铺地方法呢?你试一试，容易找出。如图(2)就是一种铺法。

第二步：下面只需证当n＜3时无法铺成。

设铺地要用m块凸形砖和n块2×1形砖。则它们占的方格数有等式4m＋2n＝6×5，即2m＋n＝15。

若n＝0，则m＝，这不可能。

若n＝2，则m＝，也不可能。

下面只要证明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染成蓝色，其他各交点染成红、蓝中的任一色，把各小方格四个顶点都染上色后，你能证明其中有三个顶点颜色相同的小方格数必为偶数吗?

图(3)

解:我们把染上色的顶点赋以数值，假定红色为1，蓝色为－1。如果小方格四顶点有三个顶点同色，另一顶点不同色，则此四个数的乘积应该是－1。如果小方格四顶点同色或者两两顶点分别同色，那么此四个数乘积为1。

设有k个小正方形四顶点中有三顶点同色，则所有n2个小正方格顶点的数的乘积为

n2－k×(－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为偶数。