全网热议的RMM第三题，到底在问什么？

作者 & 编辑 | 罗数君

文 2584字  阅读时间约 7分钟

导语：

全网火热的一道数学题，“难倒中国选手的第三题”，今天就让罗教授告诉你到底怎么解——

罗数君做梦也没想到

万年上不了热搜的数学话题

这次居然在微博上引起了不小的讨论

看这关注度，还上了热门微博

足以媲美三线小明星的八卦了

罗数君定睛一看，原来和今年的

罗马尼亚数学大师杯（RMM）有关

看来大家对本次RMM的反响很热烈

尤其是那“难倒中国选手的第三题” 

一时间关于这道题的讨论层出不穷

从本次比赛的奖牌榜就不难看出

这道题的难度非同小可——

金牌和银牌的差距

几乎全在能否解出这道题上

罗数君隔着屏幕

仿佛看到了大家求知若渴的眼神

当下不敢怠慢，立刻去请教了罗教授

在RMM官方给的答案中

第三题有两种解法，一种是官方的

另一种则署了罗教授的名字

但罗教授谦虚地表示

这个版本的回答他只是提供了思路

随后的推理证明由赛事组委会完成

这里要特别感谢我们的实习生Peter同学，他昨天连夜完成了RMM官方答案中罗教授版本的翻译工作，并加入了自己的理解和注释。但由于篇幅较长，罗数君把详细的介绍放在了今天的次条推送中，感兴趣的同学千万不要错过了！

但可能对于许多非数学专业的朋友来说，光读题就已经让人感觉怀疑人生了……

所以在这里，我们为大家做了一个通俗易懂的科普。感谢我们的实习生Jason同学，用简单的文字描述告诉了我们：这道题问的到底是什么？题眼是什么？我们这些肉眼凡胎的吃瓜群众，到底该怎么理解这道题并且进行下一步思考？

本题题目：给定任意正实数ε，请证明，除了有限个反例之外，所有正整数v都满足：所有由v个顶点和至少(1+ ε)v条边构成的图，都存在一对等长的不同简单圈（注意，简单圈不允许重复出现相同的顶点）。

但看到这道题目的时候，我们很容易被题目中图论的概念吓住，因为在初高中的学习中，我们很少提到图论，也很少会花时间了解图论中不同术语的概念。但其实中学生学习图论也大有裨益，感兴趣的朋友可以移步我们之前的文章《为什么中学生要学习图论？》。

回到题目。其实通过一些简单的介绍，很快我们就能帮同学们看明白这个问题，并且找到解题灵感。

首先，让我们了解一下这道题目中出现的图论的术语：

顶点（vertex）：图论中图（graph）的基本组成部分是顶点（vertex）和连接顶点的边（edge）

边（edge）：连接两个顶点的线叫边（edge）

圈（cycle）：图论中，圈从一个顶点起步，沿着不重复的边，不重复的顶点为途径，回到起点的闭合路径。

在一个图中，如果我们有n个顶点，而每两个点会形成一条边，所以这个图中最多存在(n-1)+(n-2)…2+1个边，也就是从n个顶点中选出2个有多少种选法。我们可以从下图中看到，这个图中一共有5个顶点，当每两个顶点都有一个边相连，这个图中一共有5个顶点，所以最多可以连成10条边。在这个图中，因为所有的点两两相连，我们可以清楚地看到5个顶点和10个边。

我们可以在这个图中找到很多圈：我们可以看到这个图中有不少长度为3的圈，我们在图中标红的两个圈就有着相同的长度。在这里，我们需要指出，在图论中的长度和我们日常生活中的长度是不一样的。图论中圈的长度是这一个圈中包含定点的数量。

现在我们可以想一想，如果一个图中的边很少，我们就很难找到圈。用相同的例子，如果我们只有一条边，我们不难看出，无论这条边连接了任何两个顶点，这一个图中都不可能存在一个圈。

现在，让我们思考一个稍难一点的问题：在一个有n个顶点且不存在圈的图中，最多能有多少条边？

我们不难想出，在一个有n个顶点的图中，如果已经存在了n-1个边，增加的任意一条边都会让这个图产生一个圈。我们可以通过下图来看一看：

这样，我们可以知道，当一个图中有n个边的时候，这个图中一定存在至少一个圈。

我们可以看出，当一个图的边越多，这个图中不一样的圈也会越来越多。现在，我们就可以更好的理解RMM的这个问题。当一个图中有v个顶点，且有(1+ ε)v条边，因为ε大于0，这个图中边的数量一定＞v，我们不难知道这个图中将会存在一些圈。这道题目的核心，就是证明出在这些图中，我们能找到两个长度相同的圈。

看懂题目了吗？恭喜你，完成了解决这道题目最简单的部分！接下来更难的部分自然是后续的推理证明了。当然了，对题目理解越深，就会有越多的解题思路和灵感。

如果你看到这里还觉得游刃有余，大可尝试动手解这道题了！如果你觉得力有未逮，那么请移步我们今天的次条推送、第三条推送。

没想到吧，今天我们还有第三条推送！之前已经提过，第二篇推送的RMM官方答案，只是罗教授提供的思路，由RMM赛事组委会推理证明的。

昨天在我们的要求下，罗教授亲自连夜赶出一份新的证明，把他的思路用自己的方法证明出来了！不过罗数君还没有来得及翻译，会在明天或者后天的推送为大家带来中文版本。想抢鲜看罗教授独家证明的朋友，请移步今天的第三条推送~

最后，让我们来听听罗教授是怎么看待这道题的——

问题3是整个比赛中最具数学趣味性的，也是最吸引我的部分。我受到一些组合学研究的启发，想出了一种解决方案。我还打算把这个问题带回去给我的博士学生，这是非常有趣的研究点。

我认为解出问题3的关键，在于对数学理念有更深层次的理解和思考。我建议在培养学生的数学能力时，既要发展高阶数学思维，同时也要用做题巩固训练；这是训练IMO的一种创新，也是一种新的挑战。

美国队员们经常聚到一起讨论研究相关的数学话题。这样的经历让他们可以更好地思考这类问题。我发现很多国家队教练都在朝这个方向转变观念。近几年，国际数学竞赛的题目开始有越来越多数学研究的影子，我们也可以预见这样的题目会被更多人认可。

最后的最后，可能有人还是会问：解这道题，到底有什么用处呢？

就现在来看，除了满足数学爱好者的“探索精神”外，可能“毫无用处”。

但当费马潜心研究数论的时候，绝对不会想到如今它在密码学中的举足轻重；当高斯在钻研统计学、线性代数的时候，也不会想到它们如今成为了机器学习的基石。

有人说数学太虚无，又有人说数学最真实。一万个数学爱好者里有一万种数学，但它们都有一个最共同的特点——他们都深爱着数学。

所有热爱数学的朋友

所有参加过RMM的选手

谢谢你们对数学的付出和热爱

喜欢这篇文章吗？欢迎给我们留言，探讨有趣的数学问题，如果你还想看其他的相关内容，也可以向我们提出来哦！ 

相关推荐