1、地图的“四色猜想”

   世界近代三大数学难题之一。四色猜想的提出来自英国。1852年，毕业于伦敦大学的弗南西斯.格思里来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家着上不同的颜色。”这个结论能不能从数学上加以严格证明呢？他和在大学读书的弟弟格里斯决心试一试。兄弟二人为证明这一问题而使用的稿纸已经堆了一大叠，可是研究工作没有进展。

    1852年10月23日，他的弟弟就这个问题的证明请教他的老师、著名数学家德.摩尔根，摩尔根也没有能找到解决这个问题的途径，于是写信向自己的好友、著名数学家哈密尔顿爵士请教。哈密尔顿接到摩尔根的信后，对四色问题进行论证。但直到1865年哈密尔顿逝世为止，问题也没有能够解决。

    1872年，英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数学界关注的问题。世界上许多一流的数学家都纷纷参加了四色猜想的大会战。1878～1880年两年间，著名的律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文，宣布证明了四色定理，大家都认为四色猜想从此也就解决了。

    11年后，即1890年，数学家赫伍德以自己的精确计算指出肯普的证明是错误的。不久，泰勒的证明也被人们否定了。后来，越来越多的数学家虽然对此绞尽脑汁，但一无所获。于是，人们开始认识到，这个貌似容易的题目，其实是一个可与费马猜想相媲美的难题：先辈数学大师们的努力，为后世的数学家揭示四色猜想之谜铺平了道路。

    进入20世纪以来，科学家们对四色猜想的证明基本上是按照肯普的想法在进行。1913年，伯克霍夫在肯普的基础上引进了一些新技巧，美国数学家富兰克林于1939年证明了22国以下的地图都可以用四色着色。1950年，有人从22国推进到35国。1960年，有人又证明了39国以下的地图可以只用四种颜色着色；随后又推进到了50国。看来这种推进仍然十分缓慢。电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的进程。1976年，美国数学家阿佩尔与哈肯在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明。四色猜想的计算机证明，轰动了世界。它不仅解决了一个历时100多年的难题，而且有可能成为数学史上一系列新思维的起点。不过也有不少数学家并不满足于计算机取得的成就，他们还在寻找一种简捷明快的书面证明方法。

2、哥尼斯堡七桥猜想

请你做下面的游戏：一笔画出如图1的图形来。 http://s1/middle/63339939g81fc604dd520&690

规则：笔不离开纸面，每根线都只能画一次。

这就是古老的民间游戏——一笔画。

你能画出来吗？

如果你画出来了，那么请你再看图2能不能一笔画出来？http://s6/middle/63339939g81fc6fcef4b5&690

虽然你动了脑筋，但我相信你肯定不能一笔画出来！

为什么我的语气这么肯定？我们来分析一下图2。我们把图2看成是由点和线组成的一种集合。图里直线的交点叫做顶点，连结顶点的线叫做边。这个图是联通的，即任何二个顶点之间都有边。很显然，图中的顶点有两类：一类是有偶数条边联它的，另一类是有奇数条边联它的。一个顶点如果有偶数条边联它的，这点就称为偶点；如果有奇数条边联它的，就称它为奇点。我们知道，能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。图2有六个奇点，四个偶点，当然不能一笔画出来了。

为什么能一笔画的图形只有上述两类呢？

有关这个问题的讨论，要追溯到二百年前的一个著名问题：哥尼斯堡七桥问题。

十八世纪东普鲁士哥尼斯堡城（今俄罗斯加里宁格勒）的普莱格尔河，它有两个支流，在城市中心汇成大河，中间是岛区，河上有7座桥，将河中的两个岛和河岸连结，如图3所示。由于岛上有古老的哥尼斯堡大学，有教堂，还有哲学家康德的墓地和塑像，因此城中的居民，尤其是大学生们经常沿河过桥散步。渐渐地，爱动脑筋的人们提出了一个问题：一个散步者能否一次走遍7座桥，而且每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。   

http://s2/middle/63339939g81fc74893c51&690

              

这个问题看起来似乎很简单，然而许多人作过尝试始终没有能找到答案。因此，一群大学生就写信给当时年仅20岁的大数学家欧拉。欧拉从千百人次的失败，以深邃的洞察力猜想，也许根本不可能不重复地一次走遍这七座桥，并很快证明了这样的猜想是正确的。欧拉是这样解决问题的：既然陆地是桥梁的连接地点，不妨把图中被河隔开的陆地看成4个点，7座桥表示成7条连接这4个点的线，如图4所示。

http://s15/middle/63339939g81fc7956496e&690

于是“七桥问题”就等价于图5中所画图形的一笔画问题了。欧拉注意到，如果一个图能一笔画成，那么一定有一个起点开始画，也有一个终点。图上其它的点是“过路点”——画的时候要经过它。现在看“过路点”具有什么性质。它应该是“有进有出”的点，有一条边进这点，那么就要有一条边出这点，不可能是有进无出，如果有进无出，它就是终点，也不可能有出无进，如果有出无进，它就是起点。因此，在“过路点”进出的边总数应该是偶数，即“过路点”是偶点。如果起点和终点是同一点，那么它也是属于“有进有出”的点，因此必须是偶点，这样图上全体点都是偶点。如果起点和终点不是同一点，那么它们必须是奇点，因此这个图最多只能有二个奇点。现在对照七桥问题的图，所有的顶点都是奇点，共有四个，所以这个图肯定不能一笔画成。欧拉对“七桥问题”的研究是图论研究的开始，同时也为拓扑学的研究提供了一个初等的例子。

　　事实上，中国民间很早就流传着这种一笔画的游戏，从长期实践的经验，人们知道如果图的点全部是偶点，可以任意选择一个点做起点，一笔画成。如果是有二个奇点的图形，那么就选一个奇点做起点以顺利的一笔画完。可惜的是，古时候没有人对它重视，没有数学家对它进行经验总结，以及加以研究。

　　今天学习欧拉的成果不应是单纯把它作为数学游戏，重要的是应该知道他怎样把一个实际问题抽象成数学问题。研究数学问题不应该为“抽象而抽象”，抽象的目的是为了更好的、更有效的解决实际产生的问题，欧拉对“七桥问题”的研究就是值得我们学习的一个样板。

3、叙拉古猜想

   大家一起来做这样一个游戏：每个人可以从任何一个正整数开始，连续进行如下运算，若是奇数，就把这个数乘以3再加1；若是偶数，就把这个数除以2。这样演算下去，直到第一次得到1才算结束，首先得到1的获胜。比如，要是从1开始，就可以得到1→4→2→1；要是从17开始，则可以得到17→52→26→13→40→20→10→5→16→8→4→2→1。自然地，有人可能会问：是不是每一个正整数按这样的规则演算下去都能得到1呢？这个问题就是叙拉古猜想，也叫科拉兹猜想或角谷猜想。

　　既然是猜想，当然至今还没有得到证明，但也没有发现反例。利用计算机，人们已经验证了所有小于100*2⁵⁰=112589990684262400的正整数，。这是葡萄牙阿弗罗(Aveiro)大学的Tomas Oliveira e Silva的工作，用了很巧妙的编程方法。因此大家在做游戏时大可不必担心会出问题。

4、汉诺塔问题

   汉诺（Hanoi）塔问题：古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上（如图）。

http://s13/middle/63339939g81fc95dbe2bc&690

    有一个和尚想把这64个盘子从A座移到B座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。在移动过程中可以利用B座，要求打印移动的步骤。

    这个问题在盘子比较多的情况下，很难直接写出移动步骤。我们可以先分析盘子比较少的情况。假定盘子从大向小依次为：盘子1，盘子2，...，盘子64。

    如果只有一个盘子，则不需要利用B座，直接将盘子从A移动到C。

    如果有2个盘子，可以先将盘子1上的盘子2移动到B；将盘子1移动到c；将盘子2移动到c。这说明了：可以借助B将2个盘子从A移动到C，当然，也可以借助C将2个盘子从A移动到B。

    如果有3个盘子，那么根据2个盘子的结论，可以借助c将盘子1上的两个盘子从A移动到B；将盘子1从A移动到C，A变成空座；借助A座，将B上的两个盘子移动到C。这说明：可以借助一个空座，将3个盘子从一个座移动到另一个。

   如果有4个盘子，那么首先借助空座C，将盘子1上的三个盘子从A移动到B；将盘子1移动到C，A变成空座；借助空座A，将B座上的三个盘子移动到C。

    上述的思路可以一直扩展到64个盘子的情况：可以借助空座C将盘子1上的63个盘子从A移动到B；将盘子1移动到C，A变成空座；借助空座A，将B座上的63个盘子移动到C。