让中国队几乎团灭的奥赛第三题,到底怎么解?

18天以前
罗数君

作者 / 罗数君

转载 / 罗博深数学


前言

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


罗数君做梦也没想到,万年上不了热搜的数学话题,这次居然在微博上引起了不小的讨论:



看这关注度,还上了热门微博,足以媲美三线小明星的八卦了。罗数君定睛一看,原来和今年的罗马尼亚数学大师杯(RMM)有关:


看来大家对本次RMM的反响很热烈,尤其是那“难倒中国选手的第三题” 。一时间关于这道题的讨论层出不穷:


从本次比赛的奖牌榜就不难看出这道题的难度非同小可——金牌和银牌的差距几乎全在能否解出这道题上。


罗数君隔着屏幕,仿佛看到了大家求知若渴的眼神,当下不敢怠慢,立刻去请教了罗教授:


RMM官方给的答案中,第三题有两种解法,一种是官方的;另一种则署了罗教授的名字。但罗教授谦虚地表示:这个版本的回答他只是提供了思路,随后的推理证明由赛事组委会完成。


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


所以在这里,我们为大家做了一个通俗易懂的科普。这道题问的到底是什么?题眼是什么?我们这些肉眼凡胎的吃瓜群众,到底该怎么理解这道题并且进行下一步思考?


本题题目:给定任意正实数ε,请证明,除了有限个反例之外,所有正整数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,我们不难知道这个图中将会存在一些圈。这道题目的核心,就是证明出在这些图中,我们能找到两个长度相同的圈。


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



如果你看到这里还觉得游刃有余,大可尝试动手解这道题了!



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


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


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


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



最后的最后,可能有人还是会问:解这道题,到底有什么用处呢?


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


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


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



版权声明:本文转载自罗博深数学,版权归属作者/原载媒体所有。



美国顶尖理工科强校来华面试,火热倒计时!

American Heritage School(美利坚海瑞学校)

美国国家数学竞赛全美第一

佛州科学博览会竞赛全州第一

国家优异学生奖”获奖人数连续九年蝉联全美私校第一



美国顶尖理工科强校1对1沟通+面试机会来袭!

您的孩子如果喜欢理工科,这将是一次不容错过的绝佳机会

名额有限,报名从速

时间:2019年3月9日(星期六)  

地点:杭州JW万豪酒店会议厅(浙江省杭州市拱墅区湖墅南路28号)


如需咨询及报名,请扫描下方二维码

微杂志 - 公众号搜索引擎

知识产权声明:版权属原作者