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

作者: , 共 2391 字

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

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这里给出了翻译,其中的概率解法尤其精妙。

2019年罗马尼亚数学大师赛第三题概率解法-已翻译成中文

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\)。这是俄罗斯出的题目。

Q. E. D.

类似文章:
数学 » 奥数
最近的罗马尼亚数学大师赛,中国队的成绩成了舆论焦点。其实,最近几年,中国奥数的成绩比往年略有下滑,同时美国和韩国队在崛起。在此介绍一些我了解到的事情,供各位吃瓜群众参考。
碎碎念 » 奥数, 付云皓, IMO
作者: 付云皓。发表于 2016 年 7 月份。作为两届 IMO 满分金牌,后来一直参与中国顶级奥数圈的教练、阅卷者和出题者工作,作者其对奥数的认识非常深刻。每个想学奥数或者对奥数有疑问的人都应该看一看。
碎碎念 » 奥数
一直以来,很多人都觉得奥数的发展需要政策扶植,比如高考加分和保送政策。这是完全没有搞清楚事实和因果关系。事实上,奥数受到的一直是政策打压而不是扶植。
以前提到过,理论计算机这门课会邀请一些正在这边访问的教授来讲课,由于是本科生,所以这些教授一般都是讲些有趣的东西,比如之前的overhang 堆积木 - 能伸出桌面多远?。今天这次课,来自 Aarhus 的Peter Bro Miltersen讲了一个很有趣的游戏问题。
数学 » open问题, 图论
孙博告诉我的,求证
注: 这个问题来自China Theory Week 2008的 Open Problems Session。
今天北京车牌摇号开奖,如果只有一倍概率,中签概率只有万分之四,估计这一辈子都中不了吧。北京车牌目前有巨大的利益,组织者如何保证其中没有猫腻呢?
想起比多中心的匿名投票协议,有一种很简单的使用盲签名的投票协议,可以做到匿名投票。