从特殊性看问题 | 目的地Destination

从特殊性看问题

从特殊性看问题

今天要和大家分享的是我当年搞竞赛时觉得最有用的一招儿:从特殊性看问题。

苏淳老师有一本小册子,书名就是《从特殊性看问题》。正是读了这本书后,我才意识到这个方法的威力。我认为对我自身竞赛水平的提高作用最大的一本书当属苏淳老师的这本,所以在进入正文之前,把这本书推荐给大家。

那到底什么是「从特殊性看问题」呢?我的理解是:先从简单情况入手,解决了简单的情况之后,通过仔细观察、分析对简单情况的解答,将其推广到一般情况,从而解决原来的问题。例如,一个关于任意正整数 n 的命题,我们可以先解决 n 比较小的情况。这个方法的核心就在于将简单情况的解法推广到一般情况。在此,我想通过两道例题来给大家展示一下如何用这个方法解题。

需要说明的一点是,我已经阔别竞赛多年,唯一记得的就是「从特殊性看问题」这七字真言。然而就是凭借这个方法,我还是可以解决 IMO 里绝大部分的 1, 2, 4, 5 题和一部分 3, 6 题。

书归正传。我们的第一道题是 2016 年 IMO 的第六题。题目如下:

在平面上有n/geq2条线段,其中任意两条线段都交叉,且没有三条线段相交于同一点。杰夫在每条线段上选取一个端点并放置一只青蛙在此端点上,青蛙面向另一个端点。接着杰夫会拍n-1次手。每当他拍一次手时,每只青蛙都立即向前跳到它所在线段上的下一个交点。每只青蛙自始至终不改变跳跃的方向。杰夫的愿望是能够适当的放置青蛙,使得在任何时刻不会有两只青蛙落在同一个交点上。

  1. 证明:若n是奇数,则杰夫总能实现他的愿望。

  2. 证明:若n是偶数,则杰夫总不能实现他的愿望。

看到这道题后,我第一个想法就是:这是一道绝好的关于「从特殊性看问题」的例题。整道题就是关于n只青蛙的故事,那我们很自然地从 n比较小的情况做起。

先来看第 1 小问。从简单情况n=3入手,试一试各种青蛙的放法。我们需要为 3 只青蛙选择出发的端点,所以一共也就 8 种情况,其中还有不少是对称的。

从特殊性看问题

我们发现这 8 种情况中的 2 种情况成功实现了杰夫的愿望。这两种情况的特点是啥?显然是所选端点不相邻嘛!其他的情况为啥不行啊?是因为有相邻的端点吗?还真是!我们发现两个处在相邻端点的青蛙总是会莫名其妙地撞上。

发现了这个特点之后,我们赶快来试一试n=5的情况。与n=3的情况不同,当n=5的时候这 5 条线段的位置关系可能有很多种情况。我们就随便画出两种,然后挑出相间的端点,看看青蛙们会不会撞在一起:

从特殊性看问题

果然,杰夫的愿望被我们实现了。于是对于所有的奇数n,我们都采取「选取相间端点」这个策略。对n=3n=5两种情况的考察使得我们对这个策略很有信心,剩下的证明是水到渠成的:我们只需固定两只青蛙,然后考虑其余线段和它们所在的两条线段相交的各种情况即可。证明细节在此作为思考题留给大家。

下面看第 2 小问。第一个想法就是:为啥我们的策略到了偶数就不行了呢?我们从简单情况n=4入手:从特殊性看问题我们还是想取相间的端点,可这时候出现了问题:我们选了同一条线段的两个端点,这是不允许的,也就是说我们不能愉快地隔一个选一个。那这就意味不管怎么选总会有两个端点是相邻的,因为隔一个选一个是选出不相邻端点的唯一方法!根据n=3时的观察,相邻端点的青蛙总会撞到一起,于是只需严格证明这一点即可。在此作为第二个思考题留给读者。

以上就是我做这道题时的所有想法。总结一下,其实最关键的就是通过考察n=3的情况找到「隔一个选一个」这个策略,并对于n=5的情况作了验证。随后我们又观察到对于n=4我们的策略不可行,原因就是不管怎么选总有两个端点相邻,这个观察直接帮助我们完成了对第 2 小问的证明。

对于这道题来说,从小n到大n的推广非常简单和自然,但并不是所有题目都是这样。下面我想给大家分享的是我对 2012 年 IMO 第 2 题的解答。虽然我做这道题很不顺利,走了很多弯路,但最终还是在「从特殊性看问题」的指引下成功给出证明。我想把我做这道题时的全部心路历程都展现出来,也许有的地方和标答相比显得有些愚钝,但对我来说,能在离开竞赛多年后靠着「从特殊性看问题」这个方法给出解答,我已经心满意足了 ☺️

下面先看题:

设整数n/geq3,正实数a_2,a_3,/cdots ,a_n满足a_2a_3/cdots a_n=1。证明:从特殊性看问题

先做一点初步的观察。首先,这是一个严格的不等式;题目还说n/geq3,为啥呢?哦,因为n=2的时候不等式很无聊且可以取等号,大概出题人不想让我们误以为对于所有的n都可以取等,真是好心啊!

下面我们就开始从特殊性看问题。来看n=3,这时不等式变成了

从特殊性看问题我想起一个常用技巧:令x=a/b,y=b/a。然后不等式就是这个样子:

从特殊性看问题很简单,直接均值不等式:

从特殊性看问题但我隐隐地有些担忧:常数部分的估计可能无法推广到一般情况。事后再看,这个担忧是有道理的。

我进而把类似的均值放缩拿到n=4来试一试。当n=4时,做类似的换元:a_2=a/b, a_3=b/c, a_4=c/a。不等式变成下面的样子:

从特殊性看问题这时,我们需要把a+b, b+c, c+a 拆分后进行均值不等式放缩,但似乎我们有无限多种选择。当n=3时,我们把a+b拆成了a/3+a/3+a/3+b/2+b/2,也就是说拆分是按照a:b=3:2做的。回到n=4 的情况,我 naive 地试了一发a:b:c=4:2:3这个比例,然而发现如此放缩之后得到的并不是 a^4b^2c^3。于是我决定待定系数按照a:b:c=1:/lambda :/mu的比例进行均值不等式的放缩。为此,我们需要下面的等式成立:

从特殊性看问题

所以我们有如下方程组:

从特殊性看问题做到这儿我觉得情况不太妙——就算我能解出来,那n很大的时候怎么办?而且还有恶心的常数要估计呢!在这个时候我终于决定放弃按照同一比例用均值不等式。之前我要按一个公用的比例放缩主要是想让不等式可以取等号,不存在放缩过了的可能性;但原不等式暗示我们有余地「乱」放缩。

那现在的计划仍然是用均值不等式,目标是放缩后左边得到a^4b^2c^3乘以一个不太复杂的常数,当然如果正好得到4^4a^4b^2c^3就再好不过了。只要先把(a+b)^2的均值不等式放缩定下来,其余两项也就确定了;所以我们先试着放缩(a+b)^2这一项。如果这个方法可行,那做分拆的时候比例一定不会很复杂。无非就是几种情况:1:1, 1:2, 2:1, 3:1之类的。一个一个试吧!运气不错,1:1就是估计(a+b)^2时的正确比例:

从特殊性看问题

把这三个式子乘起来就得到了n=4时的证明,这个证明可以推广到任意的n。总结一下,我们在n=3时发现要用均值不等式,在n=4时找到了分拆每一项的正确比例。我们并没能将n=3时的证明推广到一般情形,原因在于我们把(a+b)^3(a+b)^2化简成了(a+b)^5,也就是说n=3的的情况有些过于特殊了。这一点也是我们在使用「从特殊性看问题」这个方法时需要注意的。

从特殊性看问题

最后,分享一些心得给大家。刚开始用「从特殊性看问题」这个方法时,难免会出现解决完简单情型后就不知所措的情况。这是由于经验不足或耐心不够等原因,我们未能从简单情形及其解答中观察到足够多的规律与信息。然而只要大家勤于修炼,养成「从特殊性看问题」的好习惯,不放过任何一个用此法解题的机会,我们的解题水平就一定能因此而提高。

彩蛋思考题:在平面上有n/geq2条线段,没有三条线段交于同一点。每个线段的端点不在其他线段上(并不要求线段两两相交)。杰夫在每条线段上选取一个端点并放置一只青蛙在此端点上,青蛙面向另一个端点。接着杰夫会拍n次手。每当他拍一次手时,每只青蛙可以选择原地不动或者立即向前跳到它所在线段上的下一个交点(包括另一个端点)。每只青蛙自始至终不改变跳跃的方向。杰夫和青蛙们的愿望是能够适当选择出发端点,使得在任何时刻不会有两只青蛙落在同一个交点上,且拍完n次手后青蛙都到达了所在线段的另一个端点。

  1. 证明:若n是奇数,则杰夫和青蛙们总能实现他们的愿望。
  2. 证明:若n是偶数,则杰夫和青蛙们不总能实现他们的愿望。

来源:知乎 www.zhihu.com
作者:杨奔

【知乎日报】千万用户的选择,做朋友圈里的新鲜事分享大牛。 点击下载

分享

从特殊性看问题:等您坐沙发呢!

Leave your comment