请问这道数学题怎么解？请给出解题过程

来源：蜘蛛抓取(WebSpider) 时间：2022-09-27 11:53 标签： 她尽力自己解出那道数学题英文

编者按：在2月25日的罗马尼亚数学大师赛（RMM）上，难倒中国选手的“第三题”引起热议。近日在“湃客·镜相”栏目独家撰稿、讲述自己数学之路的美国奥数国家队主教练罗博深（Po-shen Loh）及其编辑团队在其公众号上提供了题目解法，并授权“湃客·众声”栏目转载。本文分为通俗版、简略版和英文完整版，供不同程度的读者参考，中文完整版将在之后发布。本文首发于“罗博深数学”公众号：LuoboshenMath。

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

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

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

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

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

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

罗马尼亚数学大师杯（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，我们不难知道这个图中将会存在一些圈。这道题目的核心，就是证明出在这些图中，我们能找到两个长度相同的圈。

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

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

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

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

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

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

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

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

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

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

本答案是RMM官方答案中，署名罗教授版本的翻译版。由罗教授提供思路，RMM官方委员会进行推理论证，罗博深数学实习生Peter进行翻译、注释。

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

注：本证明旨在帮助大家理解题目背后的思想，因此省略了很多严谨的细节。如果你不满足于这篇概要，欢迎访问RMM官网（）查看完整的证明。如果有其他疑问，欢迎在文章下留言，我们会尽全力解答的哦~

在开始证明之前，我们先来介绍几个图论中基本的概念：

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

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

相邻（adjacent）：如果两个顶点之间存在一条边，我们说它们是相邻的。

度数（degree）：对于任何一个顶点v，与它相临的所有顶点的总数叫做这个顶点的度数, 用deg(v)表示。

邻域（neighborhood）：对于任何一个顶点v，与它相临的所有顶点组成的集合叫做v的邻域，用N(v)表示。

路径（path）：图论中，路径的本质是一个顶点序列，它的每个顶点有一条边连接该序列中下一顶点。一条路径可能是无穷的，但有限路径有一个最先顶点，称为起点，和最后顶点，称为末点，这两个顶点都叫做端点。

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

连通性（connectedness）：如果对于图中的任何两个顶点，我们都能找到一条路径以它们为两个端点，那我们说这个图是联通的。

树（tree）：如果图符合以下标准：

1．边的数量是顶点数量减一  2．图是联通的3．图中不存在圈

环（loop）：一条连接顶点本身的边

围长（girth）：图中最短圈包含的边数，比如一个正方形的围长就是4

引理：任意固定的正实数δ，都满足：在v个顶点上，且围长至少为δv的图，最多有v+ o(v)条边。

本文是罗教授对2019年RMM第三题的独家解析，因时间仓促目前只能提供英文版，在明后天的推送中会为大家带来翻译版本，敬请期待。

（本文首发于“罗博深数学”公众号：LuoboshenMath。）

京东上的所有商品信息、客户评价、商品咨询、网友讨论等内容，是京东重要的经营资源，未经许可，禁止非法转载使用。

注：本站商品信息均来自于合作方，其真实性、准确性和合法性由信息拥有者（合作方）负责。本站不提供任何保证，并不承担任何法律责任。

印刷版次不同，印刷时间和版次以实物为准。


京东价：京东价为商品的销售价，是您最终决定是否购买商品的依据。

划线价：商品展示的划横线价格为参考价，并非原价，该价格可能是品牌专柜标价、商品吊牌价或由品牌供应商提供的正品零售价（如厂商指导价、建议零售价等）或其他真实有依据的价格；由于地区、时间的差异性和市场行情波动，品牌专柜标价、商品吊牌价等可能会与您购物时展示的不一致，该价格仅供您参考。

折扣：如无特殊说明，折扣指销售商在原价、或划线价（如品牌专柜标价、商品吊牌价、厂商指导价、厂商建议零售价）等某一价格基础上计算出的优惠比例或优惠金额；如有疑问，您可在购买前联系销售商进行咨询。

异常问题：商品促销信息以商品详情页“促销”栏中的信息为准；商品的具体售价以订单结算页价格为准；如您发现活动商品售价或促销信息有异常，建议购买前先联系销售商咨询。

我要回帖

更多关于 她尽力自己解出那道数学题英文 的文章

 

随机推荐