说说罗马尼亚数学赛中国队团灭的第三题
原创 , 图片3
2019-3-5 07:23

前几天中国队参加罗马尼亚数学竞赛惨败的消息小火了一把,尤其是第三题,只有一人得了1分,可谓团灭。网上的报道有些夸张成分,容易造成误导,好像题目很难,刷题遗漏了,又有大把关于是否该加强奥数的讨论。是否该加强奥数,关系国家发展大局,我不敢妄言,只能就事论事,就这倒题本身谈谈自己的一些不成熟想法。


早于国内报道,2月25日中午(美国时间),我就在海外论坛上看到有人贴出了“团灭”的消息。看了一下分数表,我还发现了一个不太为人注意的细节,对各国选手而言第三题似乎并没有那么难,即便是铜牌最后一名,第三题也是满分。这就有意思了。没多久有人贴出了第三题和自己的解题思路,并说这是一道送分题,于是我就懒得思考了,直接偷看答案了。看完后我基本同意送分题的观点。该题如下:

翻译成中文:

给定任何一个正实数ε,证明除了有限个正整数以外的所有正整数v,任何有v个顶点且
有大于等于(1+ε)v条边的图包含两个不同的等长简单回路。(注意简单回路中没有重复顶点)


这位大侠的评论和解题思路如下:

睡前看到这道题,两三分钟就做出思路了,写完整证明也用不了10分钟。
我一说思路,多数都能做出来吧:
1)这是一个送分的大水题;
2)这是一个计算机算法题;
3)中国队教练该刷刷Leetcode了

(本人注:Leetcode是个国外网站,很多大软件公司的应聘者到这里交流编程与算法)


另一位大侠给出了相似的思路:

这个题从直观上来看很容易接受。顶点数v大的时候,1.x倍的边数比顶点数大很多。
一棵树,也就是一个没有回路的图,是边数比顶点数小1。边数再多一点,就必须有回
路了。多余的边数可以被多回路吸收。但是吸收的速度,要考虑。如果假设没有相同边
数的回路,那么回路长度只能是,3,4,5,等等。这个吸收多余边数的速度,恐怕是
达不到1.x倍顶点数的速度。。。
 

标准答案附在本文末尾,跟第二位大侠的思路基本一致。看不懂的话其实也没啥关系,这里不想具体讲解这道题目,只想探讨一下这道题带来的一些启发。简单的说,这是一道典型又非典型的图论题。说典型,是因为其涉及的图论概念比如生成树、回路等,都是常用概念。说不典型,是因为这道题引入了正实数ε,有限个正整数以外的所有正整数v(即对于充分大的v)这样一些数学分析中常用的术语。相信学过微积分初步的朋友对这些都不陌生。


我的感悟大体有两点。第一,奥数学习不仅要培养数学技巧,更重要的是培养数学直觉


一道难题看似无从下手,苦苦思索后未果,看了解答后豁然开朗,击节叫好。很多人到此为止,就转向下一题了,然而最关键的最能提升能力的下一步,却错过了。想想解题者怎么想出这种解答方式的,比看懂答案更重要。最终的解答过程是按照数学逻辑加工后的整理版,而解题者在脑海中和草稿纸上的思考演算过程,才具有更大的学习价值。一般而言,解题高手在对数学理论的学习后形成了自己的心得体会,并将数学元素在脑海中重新建模,形成清晰可见的“数学实体”。有了这个一般性通用性的“数学实体”后,就可以以不变应万变了,解题过程中依靠对这种实体的观测与想象进行直观推理,然后把推理过程用数学语言精确描述出来。比如用微积分解题时,在脑海中浮现一个微小单位的几何结构,长度角度都能想象出来,这样可以组合成一个无穷小量,然后加上积分符号,得出一个积分表达式进行运算。这种解题过程可以依靠直觉,大大降低了思考的复杂度,提高了验算的准确度,其实质是利用人类在生活中无处不在的空间概念,利用大自然这台精确的计算机辅助我们解题。很多数学家留下的手稿大有研究价值,也是出于这个道理。


回到这道题,脑海中浮现出出生成树的样子,生成树的边加粗显示,其他的多余的边与生成树构成回路,这样就能很自然的像那位大侠一样意识到,在顶点数线性增长时,题目限制了边数线性增长,而只要能证明回路数的增长速度大于线性,那自然在顶点数足够大时结论成立。有了这样的想法,细节即便不能完全搞清楚,但7分中得个3到4分还是很容易的。只得1分,甚至0分,表明完全没有思路,这说明在学习图论生成树理论时没有深入思考为什么要研究生成树,生成树作为树的骨干有何特殊意义,而只是为了应付题目记住了一些知识点和技巧,比如Kruskal最小生成树算法。这也是“学而不思”的一种体现。


这道题的增长速率分析,实际上跟数学应用中的估算、量纲分析也很类似。ε的具体值无关紧要,只要能做定性判断即可,具体的上下界分析可以在以后研究。这也是大侠说这道题其实是个送分题的理由之一。这种估算的能力在开放性问题研究时非常实用,可以帮助我们迅速剔除调明显不对的结论,缩小研究范围,更快找到正确结论。这种直觉能力,类似于你听到一艘航母排水量只有一千吨,会立即凭本能就觉得不对。


再比如一道老题,在2N×2N的棋盘上放上3N个棋子,证明必然可以选出N行与N列,使得这些棋子全都在这N行与N列中。一种直观的思考方式是,注意到3N的这个系数3必然有其意义,意识到2N个棋子可能太少,结论太容易证明,4N个棋子可能太多,结论不成立,那么3有何特殊意义呢?再注意到2N×2N可以分成4块N×N的子棋盘,其中3块形成L形,正好是N行与N列,直觉上这个3与那个3形成联系,每个N×N子棋盘上平均放置N个棋子。于是很快就会发现对2N行按棋子数排序,选出包含棋子最多的那N行,然后分析剩下的棋子数,很容易证明都可以放进N列。


数学家不仅把数学直觉停留在草稿纸上,而且直接应用到了数学理论的表述中。最典型的例子是数学分析中“空间”概念的引入。本来这个概念是数学家用生活中的空间常识来辅助思考,后来他们发现直接用这个概念来进行描述和推演非常方便,而为了追求抽象性一般性而刻意回避这个概念反而不自然,于是干脆定义了函数空间,将几何概念引入代数。


一个好的老师比书本更有价值,其中一点就在于他可以面对面的把自己的数学直觉传授给学生,而书本篇幅终究有限,写书的人很难把自己的想法完整记录成文字。


良好的数学直觉一旦形成即不会再遗忘,脑海中对数学形体的直观化思维,是一个人数学知识的最核心部分,终生不会丢失,就像学会骑车一样。如果若干年后你再复习,发现一点印象都没有,那说明你当年学习没有建立起这种牢固内核。


能否培养并形成清晰的数学直觉,也可以作为是否有奥数潜力的自我鉴定方式。


第二点感悟,更高效的奥数学习者,还要想到更深一步:出题者是怎么想出这道题的出题者为什么要出这道题?


仅仅就这道题而言,我分析大致是这几点。第一,出题者尽量避免题目需要依赖图论中的某些定理与结论,因为这样不是考察能力而是考察刷题。第二,数学竞赛的题目越来越偏向于应用化实用化,尤其是在当前计算机科学热门的背景下。第三,出题者尽量避免出“要么零分要么满分”的题目,一道题即便做不出来也有机会得部分分数,从而给选手更多展示自己的机会,也有利于在分数上造成区分度。第三,出题者为了增大难度,没有用ε=1或某个特定值出题,而是用了个一般形式,这就加深了对增长速率这个数学概念的考察程度。


“要么零分要么满分”的题目,比如这道:在19×19路围棋盘交叉点上放满黑白棋子,其中左上右下2个角顶点是黑子,右上左下2个角顶点是白子;现考察这18×18(324)个棋盘小方块,每个方块4个顶点,求证4个顶点中黑子为奇数个(1个或3个)的小方块数是偶数。这道题见过或学习过染色理论的可以秒解,给黑子赋值1,白子赋值-1,求所有方块4个顶点的乘积,注意到边上的每个点算了两次,中间的每个点算了四次,马上得出证明,三分钟写完解答。不会的话想破头皮也想不出来。这就是“要么零分要么满分”。应该说这种类型的题目在高层的数学竞赛中越来越不受青睐,而在底层奥数培训中往往还很多见,有一定的误导性 。


出题者本身都是精通高等数学的专家,在出高中竞赛题时,他们反而面临许多约束。认识到这一点,可以使得解题者充满必胜信心。一个出题思路是从初等数学超出课本的范畴去出题。比如欧式几何在近代仍有发展,有很多复杂的结论,远超课本教学范畴,比如《近代欧式几何学》(https://book.douban.com/subject/1551510/)。另一个方向是从高等数学内容中抽取可以用初等数学知识解答的特例,比如递推方程式的求解,有一整套完整的理论,比如齐次非其次,其中某些特殊形式可以用初高中知识解答。第三个方向是不同数学领域交叉,这类的在应用数学类的杂志上有很多有趣问题研究,罗马尼亚这第三题就是一例。还有些别的出题方式,超出我的想象能力了,因为我毕竟不是出题者,只能从看到的题目去揣测。


对每道奥赛题目,在完全弄清楚解答过程,思考了如何得出这个解答过程后,有机会的话,想想这道题涉及哪些基本知识点?出题人是怎么从基本题目组合变形得出这道题目的?题目中的重要参数能不能改变?改变后题目是否还成立?如果不成立,结论能否修改后成立?(比如上面围棋子的题目,4个角顶点只要黑子正好偶数个包括0个,结论都成立,而 4个角顶点的黑子如果正好奇数个,则待证结论只需改成奇数个即可。)题目中的具体参数,能否一般化(比如罗马尼亚这道题就对ε进行了一般化)?这样的学习,就是举一反三的过程,充分利用了每一道题目,不仅获得了技能,也提升了能力。只看刷题的数量,是不行的。


以上是自己的一点不成熟想法,仅供参考。毕竟不是专业的奥数培训人员,只能管中窥豹。


为了内容的完整性,最后附上第三题的标准解答。

归巢鸟文

回应9 收藏11
2月前
请问一下,您觉得孩子学奥数的前提或者说觉得孩子有发掘做奥数题的潜质有哪些?
2月前
👍👍👍👍👍👍👍👍
2月前
完全看不懂的~~~~~
2月前
不明觉厉啊👍👍👍
2月前
不明觉厉,不明觉厉!
2月前
Julia祝 请问一下,您觉得孩子学奥数的前提或者说觉得孩子有发掘做奥数题的潜质有哪些?
正常课内数学学得比较轻松,课外对趣味数学书有兴趣能自主看进去吧
2月前
数学看不懂,但是深以为然。
2月前
意思是中国队忙着刷题整套路去了 忘了建立直观的数学图像?跟奥数培训思路有关系吗
2月前
仲夏晚风 意思是中国队忙着刷题整套路去了 忘了建立直观的数学图像?跟奥数培训思路有关系...
可能底层中层老师培养思路 顶层的认为选上来的基础很好 赶紧多刷题吧……只是猜想
发布