1_RjE1EQs2LCJrnysAHYZrWg.png
25日，第11届罗马尼亚数学大师赛在罗马尼亚首都布加勒斯特闭幕。以上海队为班底的中国队因为在第三题上遭遇滑铁卢，最终无人获得个人金牌，团体总分也只能名列第六。
消息传来，网络上又掀起了一轮对禁奥令和奥数培训的讨论。
各路观点都有着一定的道理，就我自己的认知，首先，近年来中国队在国际奥数竞赛（IMO）和包括罗马尼亚数学大师赛上的统治力无疑是在下降之中的，这背后的原因有很多，比如中学生学生总人数的减少、比如优秀学生在不同教育体系中的分流，比如美国等其它主要竞争对手也实行了举国培训和选拔机制，比如禁奥令在客观上带来的负面影响等等。竞赛成绩下降是多个因素综合下来的结果，简单地归于禁奥令确实比较武断。
其次，中国队在这一届罗马尼亚数学大师赛上的表现其实还过得去，并不是媒体所描绘的“惨败”。除了第三题，中国队在其它5道题上的得分还是很高的，两个人在5道题上得了满分，另外两个人在4道题上得了满分。如果在第三题上多少有些收获，那么2-3块个人金牌还是妥妥的。正如罗马尼亚数学学会会长戈洛甘所评价：中国队队员是碰到了黑天鹅事件。
那么，传说中让中国队惨败的第三题到底长什么样呢？
题目的英文原文是这样的：
网上有人把它翻译成了中文，翻译还是蛮准确的：
第三题。给定任何一个正实数e，证明对于除了有限个正整数以外的所有正整数v，任何有v个顶点并且有大于等于(1+e)v条边的图至少包含两个相互不同的等长简单回路。
（请记住，简单回路的概念意味着该回路中的顶点不能重复）
这道题来自于俄罗斯，是一道图论题。
如果你已经看到了这里，不妨再多花两分钟看看我用“人话”来解释一下。
假设在国外生活着一群中国人，人数为v，他们两两之间要么相互认识，要么相互不认识。现在给定任意一个实数e，试证明除了有限的某些v以外，对于其它任意的正整数v来说，拥有v个人的华人社区，且其中有(1+e)v对人两两相互认识，那么这个华人社区中一定存在两个不同的简单“朋友回路”。所谓“朋友回路”，即若干个人可以排成一个圆圈，圆圈中每个人都和相邻的两个人两两互相认识。
这是一道典型的图论题。图是图论研究的主要对象，它由顶点和边以及它们之间的拓扑关系组成，在上面这个例子中，每个人就是一个顶点，他们两两互相认识就是一条边。图论对于将生活中实际问题的抽象化很有帮助，同时也是计算机科学中数据结构的基础。
现在大家公认的最早的图论研究，是十八世纪中叶数学家欧拉解决的哥尼斯堡（Königsberg）七桥问题。当时属于普鲁士的哥尼斯堡被普列戈亚河划分为北岸和南岸，河流中间还有若干个小岛，两岸和小岛以及小岛之间通过若干个桥梁相连。当时有一群闲得发慌的大学生，他们选定了北岸、南岸以及河中两个小岛一共四个地点、以及它们之间的七座桥梁，试图找出能够遍历七座桥梁且每座桥梁只经过一次的路径。
这个问题引起了欧拉的兴趣，他证明了符合条件的路径并不存在，并将它拓展到了一笔画问题，指出对于拥有多于两个奇数顶点的图，无法用一笔画出。
左图只有有两个奇数顶点，用红色星号标注，从一个奇数顶点出发到另一个奇数顶点结束，可以一笔画出。右图的“田”字图，有四个奇数顶点，因此不能一笔画出。
再回到“黑天鹅”。
一个直观的理解是：如果e很小，那么对于比较小的v来说，显然是不一定存在这样两个等长的简单回路的。当顶点数v增长时，边数(1+e)v以线性方式增长，而可能存在的不等长的简单回路的个数的增长速度一定要低于线性，这样才能使得当v增长超过一个阈值时，增长的边数使得图中一定存在两个等长的简单回路。
另外，在简单回路数量一定的情况下，连通图可以“消耗”更多的边，所以作为对论题最不利的情况，可以假设图是连通的。对于连通图来说，不存在简单回路、具有v个顶点的树形结构最多可以拥有v-1条边。
我们以e = 0.2为例来理解一下。
v = 4时，最多拥有C(4, 2) = 6条边，无回路的树形结构最多有3条边（左图），拥有不同长度简单回路的图最多可以有4条边（中图）。而(1+e)v = 4.8，所以拥有4个顶点、5条边的图一定具有两个长度相同的简单回路。如右图，不论连接哪条红线，都将生成另一条长度为3的简单回路。
v = 5时，最多拥有C(5, 2) = 10条边，无回路的树形结构最多有4条边（左图），拥有不同长度简单回路的图最多可以有6条边（中图）。而(1+e)v = 6，所以拥有5个顶点、6条边的图不一定具有两个长度相同的简单回路。当边数增长到7时，图中才会出现两个长度相同的简单回路，如右图，连接红线时，将生成另一条长度为4的简单回路。
v = 6时，最多拥有C(6, 2) = 15条边，无回路的树形结构最多有5条边（左图），拥有不同长度简单回路的图最多可以有7条边（中图）。而(1+e)v = 7.2，所以拥有6个顶点、8条边的图一定具有两个长度相同的简单回路。如右图，连接红线时，似乎生成的是长度为5的简单回路，但考虑顶点A-B-C-D-A这条回路，它的长度为4，是另一条长度为4的回路。
因此，对于e = 0.2来说，v = 5就是那个有限个正整数的例外；对于其它有v个顶点的图来说，拥有1.2v条边的图一定存在着两条不同的等长简单回路。
有人可能要问，为什么这些例子里树形的结构都被画成了没有任何分叉的直链？这是因为在顶点数v确定的情况下，直链树的深度是最大的，即v–1；而对于完全二叉树来说，其高度在ln(v)的数量级上，任意两个顶点之间的距离最大为2ln(v)。在边长为(1+e)v的情况下，和直链的相比，二叉树结构的图所能形成的不等长简单回路的数量更少。（注意，这个结论并没有得到严谨的证明。）
那么，对于直链的结构，其能形成的不同长度的简单回路可以简单地用下图表示。
图中一共形成了n个简单回路，其长度分别为3、4、5……n+2，容易得到最后一个顶点x的序号为 (n+1)n/2+2。因此，对于存在n个不等长简单回路的直链来说，(n+1)n/2+2 <= v。（注意，这个结论并没有得到严谨的证明。）
这样，我们可以看到对于确定的e，图中可能存在的不等长简单回路的数量n的增长速度大致正比于v的平方根，而边数的增长速度正比于v，所以在v达到一定阈值时，边数(1+e)v减去直链骨架的边v-1后剩余的边数ev+1一定会大于n，从而在图中出现两个及两个以上不同的等长简单回路。
上述的推导并没有经过严格证明，只是为这一“黑天鹅”竞赛题提供了一种理解的方式和解题思路。严谨的证明过程请参考罗马尼亚数学大师赛官方网站【1】。
再过四个多月，第60届国际奥林匹克数学竞赛将在英国的巴斯举行，曾经的IMO霸主中国队已经连续四年无冠，今年的形势仍然不够乐观，能保持团体三甲应该算是一个可以接受的结果吧。
三十年河东，三十年河西。七桥所在的哥尼斯堡、德意志民族的龙兴之地，现在早已归属俄罗斯，名字也改作加里宁格勒。普列戈亚河中的两个小岛依旧在，七桥中却有两座桥毁于历史中的战火，如今的人们从小岛出发，可以轻易地走遍五座桥而不重复。
古今多少事，都付笑谈中！
参考出处：
题图照片：https://medium.com/basecs/k%C3%B6nigsberg-seven-small-bridges-one-giant-graph-problem-2275d1670a12
文\Athlon_BE
2019.3.2
网友评论