2019 年罗马尼亚数学大师赛第三题

这次中国队在罗马尼亚数学大师赛败北，引起巨大的舆论论战，甚至上了人民日报的评论。以前从来没出现过这种情况。作为吃瓜群众，觉得特别有意思。

1. 2019 年大师赛的一些基本情况

罗马尼亚数学大师赛比赛一共 6 个题目，每个题目 7 分。每个国家队有 4 名正式队员，团体成绩取 4 名队员的前三名之和（即去掉表现最差的一名队员）。这种做法对表现最差的队员压力很大，被开除出团体了。

中国队派出了 6 名队员，其中 4 名正式队员，另外两名队员身份不明，可能算替补。其他国家中，韩国队和美国队都只有四名正式队员，但俄罗斯也有两名替补。

中国队的 4 名正式队员的成绩分别为 35 ， 23 ， 31 ， 35 （注意满分为 42 分）。去掉表现最差的 23 分，表现最好的三名正式队员总得分为 101。而美国队表现最好的三名队员得分分别为 40 ， 39 ， 38 ，总得分为 117 ，比中国队足足高了 16 分。除了美国队，还有俄罗斯、韩国、以色列、塞尔维亚四个国家的总分比中国队高。中国队的团体总分只排到第六名。

中国队有名替补的也得了 35 分，但不能计入团体成绩，否则总得分还能高 4 分。

成绩详情可见官网：http://rmms.lbi.ro/rmm2019/index.php?id=results_math。

2. 大师赛第三题

这次中国队最大的失分点便在第三题。6 个队员在这一题上总共只得了区区一分，可以算是全军覆没。美国队团体分在这一题上得了 17 分。除这一题外的其它五个题，中国队和美国队是战平的。

韩国队在这一题上的表现也不好。如果不算这一题，韩国队就能排第一名。

2.1. 第三题原题

那这一题到底是什么呢？题目如下：

Problem 3. Given any positive real number \(\epsilon\), prove that, for all but finitely many positive integers \(v\), any graph on \(v\) vertices with at least \((1 + \epsilon)v\) edges has two distinct simple cycles of equal lengths.

(Recall that the notion of a simple cycle does not allow repetition of vertices in a cycle.)

Russia, Fedor Petrov

这个题目的distinct容易让人误解为这两个圈的顶点不能重合，但其实两个圈的边不完全一样就可以了。

翻译成中文为：

对任意\(\epsilon 0\)，当\(v\)足够大时，任意\(v\)个点，\((1+\epsilon)v\)条边的无向图，必定存在两个相同长度的简单圈。其中简单圈是指图中顶点不重复的圈。

2.2. 第三题的官方解答

官方解答见：http://rmms.lbi.ro/rmm2019/index.php?id=problems_math。

https://mp.weixin.qq.com/s/nZbym4t9rOKFP-5ROluL7g这里给出了翻译，其中的概率解法尤其精妙。

2.3. 更直接的一个解答

这个从某个群里看到的，作者是大名鼎鼎的「付」。该证明非常直观和简单。

首先，可假设图中的简单圈的个数最多\(v\)个圈，否则已经必定存在同等长度的简单圈。

简单取 \(m=\sqrt{v}\)。假设图中的某条边存在于超过\(m\)个简单圈中，我们就去掉这条边，然后证明在剩下的图仍有相同长度的的简单圈（当\(v\)足够大时）。

持续这么操作，直到任何一条简单边最多属于\(m\)个简单圈。这个操作将去掉最多\(v/m\)条边，还剩下至少\(v(1+\epsilon-\frac1m)\) 条边。

我们知道对于已经有\(v+f\)条边，至少有\(1+f\)个简单圈。因此剩下的边至少有 \(c=v(\epsilon-\frac1m)\)个简单圈。如果这些简单圈的长度都不一样，那么所有简单圈的长度之和至少为\(1+2+\cdots+c=\frac{c(c+1)}2\)。

从另一个角度，由于每条边最多属于\(m\)个简单圈，因此圈的边数总和最多为\(s=v(1+\epsilon)m\)。

这样我们有不等式：

$$ s \geq \frac{c(c+1)}2 $$

但从数量级上看左边的\(s \sim v^{\frac32}\)，而右边的\(\frac{c(c+1)}2 \sim c^2 \sim v^2\)。对于足够大的\(v\)，该表示式不可能成立，因此必定存在长度相同的简单圈。

其实这种做法可以将多余的边数下降到\(\sqrt{v}\)的量级，即当边数大于\(v+\Theta(\sqrt{v})\)时，便必定存在长度相同的简单圈。

3. 题目背景

在同一个群里，有人提到题目的背景，转发如下：

该题的原型来自数学大师 Erdos 提出的：即一个 v 个顶点的简单图，至少要加入多少条边才会出现 2 个长度一样的圈？

后来被图论大师 Bondy （滑铁卢大学，法国人）列入自己的著名教材 Graph theory with application 中作为 open problem。

一个很粗略的上界是\(2v\)，比较精确的上界在 1998 年由乔治亚州大学任教的陈冠涛教授提出为\(v+O(c\sqrt{v})\)，后来厦门大学赖老师证明了当\(v\)趋向无穷大的时候，\(c\)趋向 2.04。

RMM problem3 就是这个问题的弱化版本，证明上界小于\(n+\epsilon n\)。这是俄罗斯出的题目。

作者暂无likerid, 赞赏暂由本网站代持，当作者有likerid后会全部转账给作者（我们会尽力而为）。


Support author:
Author's Filecoin address:
Or you can use Likecoin to support author: