攻克数学难题是一个艰难的过程（现代数学上的三大难题）

现代数学上的三大难题归纳为⑴20棵树植树问题，⑵四色绘地图问题，⑶单色三角形问题。

20棵树植树问题，每行四棵，古罗马、古希腊在16世纪就完成了16行的排列，1 8世纪高斯猜想能排18行，19世纪美国劳埃德完成此猜想，20世纪末两位电子计算机高手完成20行纪录，跨入21世纪还会有新突破吗？

四色绘地图问题,是相邻两国不同着一色，任一地图着色最少可用几色完成着色 ？五色已证出，四色至今仅美国阿佩尔和哈肯，罗列了很多图谱，通过电子计算机逐一理论完成，全面的逻 辑的人工推理证明尚待有志者。

单色三角形问题,是任三人中可证必有两人同性，任六人中必有三人互相认识或互相 不认识（认识用红线连，不认识用蓝线连，即六质点中二色线连必出现单色三角形）。 单色三角形研究中，尤以不出现单色三角形的极值图谱的研究更是难点中之难点，热门中之热门。

1.与世纪同行的二十棵树植树问题

很久很久以前，阿拉伯数字王国的国王过20岁生日，罗马数字王国派人送来了20棵珍贵的树，作为生日礼物。

阿拉伯数字国王十分高兴，他命令"20"大臣将这20棵树栽在宫廷花园里，每行要有4棵，还要使行数最多。这可是一个很难很难的问题啊。"20"大臣张榜招贤，凡是能巧妙地栽这20棵树的人将有重赏。可是，谁也设计不出来。

"20"大臣日夜思索，翻了大量的资料，又用石子进行了一次次的试验。他画了成千成万个图样。画着，试着，忽然，他眼睛一亮，看到了一张极其美妙的图案。

"20"大臣立即把图案奉献给国王。国王见了非常高兴，"20"大臣指着图案对国王说："陛下，您看，图中所栽的树不论横数、竖数或斜数，每行都是4棵，这样最多18行。"

国王赞叹不止，说："这样美丽奇妙的植树图案，我在任何公园都没有看见过，简直太美妙了。我要重重地赏您！"

"20"大臣站了起来，笑了笑说："陛下，别赏我，这并不是我发明的。"

"什么？这不是你的发明？"国王问。

"对，这是一位名叫山姆·劳埃德的数学家发明和设计的，我只是把他的图案用到植树问题上来。""20"大臣据实说。

"好，好，你能用上这个图案，也是有功的。"说着，国王宣布了对"20"大臣的奖赏，并将这个图案命名为"20图案"，是世界上最美丽的植树图案。

国王立即派人按照"20图案"把20棵树栽在宫廷的花园里。从此，这美丽的植树图案就一直流传至今。

20棵树植树问题，简单地说，就是：有20棵树，若每行四棵，问怎样种植 （组排），才能使行数更 多？几个世纪以来一直享誉全球，不断给人类智慧的滋养，聪明的启迪，伴随人类文明几个世纪，点缀装饰于高档工艺美术的百花丛中，美丽经久不衰、与日俱增且不断进步，不断发展，在人类文明的进程中更加芬芳娇艳，更加靓丽多采。 [来源:学#科#网Z#X#X#K]

20棵树植树问题，源于植树，升华在数学上的图谱学中，图谱构造的智、巧、美又广泛应用于社会的方方面面。 早在十六世纪，古希腊、古罗马、古埃及等都先后完成了十六行的排列并将美丽的图谱广泛应用于高雅装饰建筑、华丽工艺美术（图1）。进入十八世纪，德国数学家高斯猜想20棵树植树问题应能达到十八行，但一直未能见其发表绘制出的十八行图谱。直到十九世纪，此猜想才被美国的娱乐数学大师山姆·劳埃德完成并绘制出了精美的十八行图谱，而后还制成娱乐棋盛行于欧美，颇受人们喜爱（图2）。

进入20世纪，电子计算机的高速发展方兴未艾，电子计算机的普及和应用在数学领域中也大显身手，电子计算机绘制出的数学图谱更是广泛应用于工艺美术、建筑装饰和自然科学领域。数学上的20棵树植树问题也随之有了更新的进展。在二十世纪七十年代，两位数学爱好者巧妙地运用电子计算机超越数学大师山姆·劳埃德保持的十八行纪录，成功地绘制出了精湛美丽的二十行图谱，创造了20棵树植树问题新世纪的新纪录并保持至今（图3）。

星移斗换，今天，人类已经从20世纪跨入了21世纪的第一个年代。20棵树植树问题又被数学家们从新提出：跨入21世纪，20棵树，每行四棵，还能有更新的进展吗？数学界正翘首以待。国外有人曾以二十万美金设奖希望能有新的突破，随着高科技的与日俱进和更新发展，期望将来人类的聪明智慧与精明才干能突破现在20行的世界纪录，让20棵树植树问题能有更新更美的图谱问世，扮靓新的世纪。

2. 地图中的数学难题——四色定理

四色问题又称四色猜想、四色定理，是世界近代三大数学难题之一。地图四色定理（Four color theorem）最先是1872年由一位叫格斯里（Francis Guthrie）的英国大学生提出来的。

四色问题的内容是"任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。"也就是说在不引起混淆的情况下一张地图只需四种颜色来标记就行。

用数学语言表示即"将平面任意地细分为不相重叠的区域，每一个区域总可以用1234这四个数字之一来标记而不会使相邻的两个区域得到相同的数字。"这里所指的相邻区域是指有一整段边界是公共的。如果两个区域只相遇于一点或有限多点就不叫相邻的。因为用相同的颜色给它们着色不会引起混淆。

1913年，美国著名数学家、哈佛大学的伯克霍夫利用肯普的想法，结合自己新的设想；证明了某些大的构形可约。后来美国数学家富兰克林于1939年证明了22国以下的地图都可以用四色着色。1950年，温恩从22国推进到35国。1960年，有人又证明了39国以下的地图可以只用四种颜色着色；随后又推进到了50国。看来这种推进仍然十分缓慢。

高速数字计算机的发明，促使更多数学家对"四色问题"的研究。电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的进程。就在1976年6月，在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿个判断，结果没有一张地图是需要五色的，最终证明了四色定理，轰动了世界。

这是一百多年来吸引许多数学家与数学爱好者的大事，当两位数学家将他们的研究成果发表的时候，当地的邮局在当天发出的所有邮件上都加盖了"四色足够"的特制邮戳，以庆祝这一难题获得解决。

但证明并未止步，计算机证明无法给出令人信服的思考过程。问题影响一个多世纪以来，数学家们为证明这条定理绞尽脑汁，所引进的概念与方法刺激了拓扑学与图论的生长、发展。在"四色问题"的研究过程中，不少新的数学理论随之产生，也发展了很多数学计算技巧。如将地图的着色问题化为图论问题，丰富了图论的内容。不仅如此，"四色问题"在有效地设计航空班机日程表，设计计算机的编码程序上都起到了推动作用。

为何在无法给出严密证明的前提下，数学家们仍能声称这一难题已被解决呢？1976年，通过100亿个四色地图的成功判断，我们用事实证明了它的正确。而如此庞大的数据支持，自然要仰赖于服务器优越的计算能力。

3. 于无声处听惊雷--单色三角形问题

空间里有n个点，任意三点不共线。每两个点之间都用红色或者黑色线段链接。如果一个三角形的三条边同色，则这个三角形是单色三角形。对于给定的红色线段列表，找出单色三角形的个数。

分析：由于三角形总数C(n,3)，所以求出异色三角形个数就求出了同色三角形个数。用暴力枚举的方法，我们将遍历所有的三角形，时间复杂度为O(n^3),则必定超时。而经过推敲，我们会发现这样的对应关系，一个异色三角形存在两个顶点，在该三角形中与它们相邻的两边是不同色的；而对从一个顶点出发的两条异色边都属于一个异色三角形。这是个一对二的关系。设第i个点连接了ai条红边、n-1-ai条黑边，这些边一定属于ai(n-1-ai)个不同的异色三角形。由于异色三角形都会被考虑两次，所以最终的答案为ans/2。这个思想只需要从第一个顶点遍历到最后一个顶点，所以时间复杂度是O(n)。

例1. 17点 三色 求证至少有两个单色三角形给出无三点共线的17个点，每两点之间连以线段，并任意染成红、黄、蓝三色中的一个，求证：在这些线段构成的所有三角形当中，至少有两个单色三角形.

解析：最少角度想：17÷3=5... 2,3个抽屉现各5个，还有2个，可放于1个或2个抽屉,故最少有1个抽屉是6个或7个。即至少有两个单色三角形。

例2． （美国普特南数学竞赛题）17 名科学家中每两名科学家都和其他科学家通信，在他们通信时，只讨论三个题目，而且任意两名科学家通信时只讨论一个题目，证明：其中至少有三名科学家，他们相互通信时讨论的是同一个题目。

证明：视17 个科学家为17 个点，每两个点之间连一条线表示这两个科学家在讨论同一个问题，若讨论第一个问题则在相应两点连红线，若讨论第2 个问题则在相应两点连条黄线，若讨论第3 个问题则在相应两点连条蓝线。三名科学家研究同一个问题就转化为找到一个三边同颜色的三角形。

考虑科学家A，他要与另外的16 位科学家每人通信讨论一个问题，相应于从A 出发引出16条线段，将它们染成3 种颜色，而16=3×5 1，因而必有6=5 1 条同色，不妨记为AB1，AB2，AB3，AB4，AB5，AB6 同红色，若Bi（i=1，2，…，6）之间有红线，则出现红色三角线，命题已成立；否则B1，B2，B3，B4，B5，B6 之间的连线只染有黄蓝两色。

考虑从B1 引出的5 条线，B1B2，B1B3，B1B4，B1B5，B1B6，用两种颜色染色，因为5=2×2 1，故必有3=2 1 条线段同色，假设为黄色，并记它们为B1B2，B1B3，B1B4。这时若B2，B3，B4 之间有黄线，则有黄色三角形，命题也成立，若B2，B3，B4，之间无黄线，则△B2，B3，B4，必为蓝色三角形，命题仍然成立。

说明：（1）本题源于一个古典问题--世界上任意6 个人中必有3 人互相认识，或互相不认识。