The Four Color Theorem & Counterexample

Presentation on theme: "The Four Color Theorem & Counterexample"— Presentation transcript:

1 The Four Color Theorem & Counterexample
大家好，我是赵新榆，今天要讲的内容是四色定理及其反例。当然，这个反例是带引号的，因为四色定理已经通过计算机被证明了。 Ps: of course all the counterexamples are wrong by now. made by 赵新榆

2 Covering it with 4 colors Extention1: Adding the surrounding
PART 01 PART 02 PART 03 PART 04 Martin Gardner and his shenanigan Covering it with 4 colors Extention1: Adding the surrounding Extention2: N colors theorem 本次展示分为四个部分，第一部分是介绍背景中这张图的来历以及相关人物，第二部分是分析如何用四种颜色涂满整张图。第三部分是对原图的一个小拓展。第四部分则是对四色定理在三维曲面中的拓展。

3 Martin Gardner and his shenanigan
PART 01 Martin Gardner and his shenanigan Who is Martin Gardner? When and why did he put forward it? Did he really come up with a counterexample? 首先看第一部分，马丁·嘉得纳和他的恶作剧。谁是马丁嘉德纳？他是什么时候，出于什么原因提出的这个关于四色定理的反例？这个反例驳倒了四色定理吗？

4 Background: Introduction to Martin Gardner
· An American popular mathematics and popular science writer ·Interests: scientific skepticism, micromagic, philosophy, religion, and literature—especially the writings of Lewis Carroll · The long-time “Mathematical Games” columnist in Scientific American 我来介绍一下马丁·嘉德纳。马丁·嘉德纳是美国数学家和美国当代最伟大的数学科普作家，这是他的主要职业。但实际上他的才华远不止这点，他还在批判伪科学、魔术、哲学、宗教、文学等领域都颇为精通。虽说他是数学家，但是他最成功的作品却是对刘易斯·卡罗尔（爱丽丝梦游仙境作者）的两部爱丽丝作品的注释本。注释本累计卖了上百万册。同时他还被誉为20世纪最重要的魔术师之一。从某种意义上讲可以说他是个不务正业的数学家。他还是个高产的作家，一生发表了100多本书。最后，他在杂志《科学美国人》开了一个数学游戏的专栏并且持续了25年。比如这个著名的“缺失的正方形”问题就是他在这个专栏里提出的。

5 Time: April Fools’ Day in 1975
Martin Gardner's April Fool's Map Time: April Fools’ Day in 1975 It was punished in the magazine Scientific American 让我们来看这张图。这张图发表于1975年四月一日愚人节当天的《科学美国人》杂志上。这张图的特点就是每块区域都与0其他多块区域相邻，最多的一块甚至和10块区域相邻。所以对于填涂颜色的要求比较高，一个不注意就容易涂错.显然这张图肯定是满足四色定理的，不然关于四色定理的讨论就可以到此为止了。

6 Solutions with 4 colors PART 02
那么我们应该如何快速地用四种颜色去解这张图呢？是否存在一些技巧呢？ Is there any tips to solve it quickly and accuratedly?

7 Tips: Start from outside or inside? 2.How is the routine?
Covering it with 4 colors ⇓ Here we start Tips: Start from outside or inside? 2.How is the routine? 3.Which to choose when there are two or more choices? 首先给大家展示一下，这个是我花了一小时得到的第一个解。虽然一些边边角角的地方涂得不是很好，但是大家应该还是能看出来这张图满足四色定理。接下来是一些关于解题的技巧。首先确定大方向：从内到外还是从外到内？我的建议是从外到内，因为很明显最外层的几个区域的相邻区域数量更多，如果选择从内到外，很有可能发生大块区域的相邻区域中四种颜色都存在，这样就解不出，而且发现这种情况的时候往往是在最后阶段，浪费的时间就比较多了。而从外到内不仅能较早地对里面的小区域的颜色进行限定，并且即使出现涂色错误的情况，也往往只要调整最后几步就可以解决。因此最佳的选择是从外到内。2.推演路径的选择。我的建议是螺旋状向内推进，就像吃大大卷一样。这是由于图形的形状倾向于螺旋状。并且最好是从螺旋线的最外头开始，如图，那么为什么是左上角而不是右下角呢？我们可以添加一条辅助线。这样就容易看出来很明显左上角才是整个螺旋的起始点。3.当存在两到三种颜色可供选择时，如何选择？

8 Covering it with 4 colors
得到第一个解法花了我一个小时，但是得到第二个解只用了10分钟，其中第二种解法在推算的过程中更加注重斜线下的对应关系。关于颜色的选择共有两种情况1. （假如我们不把图形外看成一个无界的区域的话）三种颜色的选择一般是最外层的一圈这种时候我认为是没有影响的。如图balabala 2.内圈存在两种颜色选择的时候：看下一步/找斜线的颜色 balabala

9 How many solutions are there in total?
Covering it with 4 colors Q: How many solutions are there in total? I never dreamed anyone would take it seriously, yet it produced more than a thousand letters from readers who did not recognize the column as a hoax. 那么问题来了：这张图总共有多少种解法？解法数一定是有限的，但是具体有多少种我也不确定，因为在推演的过程中有多处需要经历多种颜色的选择，每个选择可以产生更多的分支，并且也没有人去系统地分析过这张图。我这里就引用嘉德纳的原话来回答了。我从来没想过会有人认真地对待它，但是它还是使得数千个读者写信给我，显然他们并没把它当做一次恶作剧。

10 Extention1: Adding the surrounding
PART 03 Extention1: Adding the surrounding 可能有人会问，如果把最外层看做一个区域，这图还能有解吗？会不会增加难度？ Will it be more difficult?

11 Covering it with 4 colors
事实上依然是有解的，只不过是在原题的最外层的颜色使用上增加了一些限制，从三种颜色的选择削减到了两种。

12 实际上讲并没有变难，因为这相当于是把原题的最外层当做内层来看。事实上，我第三次解题时只用了6分半的时间。

13 Extention2: N colors theorem
PART 04 Extention2: N colors theorem 拓展2：四色定理在三维空间中的情况 What will it be like in three dimensions?

14 2. On the sphere or cylinder Equivalent to that on the plane
N Colors Theorem in Three Dimensions 1.In reality No limit 2. On the sphere or cylinder Equivalent to that on the plane 3.On the torus 7 colors 1.在现实里一般的三维空间中，由于空间中可以存在无数不相交的异面直线，所以最小色数是没有限制的。2.在球体或者圆柱体上，这种情况等价于平面 3.在封闭的圆环上，最小色数为7 4.我们对四色定理进行一般化。首先介绍一下在拓扑学中曲面亏格的定义：若曲面中最多可画出n条闭合曲线同时不将曲面分开，则称该曲面亏格为n。在实的闭曲面中亏格就是洞的数目。比如封闭圆环的亏格就是1对于一个可定向的曲面，涂满区域所需要的最少颜色数p和亏格g的关系式如图 4.Generalizations g= genus

15 Reference https://en.wikipedia.org/wiki/Four_color_theorem
2. 3. 4. 5.

16 Thank You All! 感谢大家的聆听（Ps：莫比乌斯带亏格为1，但是它不是可定向的曲面，所以上述公式对它不适用。另：莫比乌斯带的最小色数为6(即6色定理）