【附】为便于编辑修改,特提供纯文本文档如下:
2018联赛加试压轴题(组合数论)思路分析
冯跃峰
2018联赛加试试题的难度相对平稳,只有最后一道组合数论题较难。颇为遗憾的是,本次考试没有纯粹的组合问题:从严格意义上讲,第3、4题都是以数论知识为背景的组合问题,它们属于组合数论的范畴。
下面是我们对压轴的组合数论题解答的思路分析。
【题目】数列{an}定义如下:a1是任意正整数,an+1是与Σi=1nai互质,且异于a1,a2,…,an的正整数。试证:每个正整数都在数列{an}中出现。(2018高中数学联赛加试第4题)
【题感】从目标看,要证“每个正整数都在数列{an}中出现”,自然想到对正整数进行归纳。但从条件看,只给出了数列的定义:(an+1,Sn)=1,an+1异于a1,a2,…,an,且an+1最小。这些都无法建立相继正整数n与n+1之间的联系,因而无法对正整数本身进行归纳,只能对正整数的某种数量属性归纳(分批归纳,同一个属性含有多个正整数)。
应考察正整数的什么属性呢?不妨从特例入手,取一个具体的数列{an}来考察,从中发现规律。
此外,注意到aN+1+SN=SN+1,结合辗转相除法,可知(an+1,Sn)=1有两种等价表示:(an+1,Sn+1)=1,(Sn+1,Sn)=1。
【研究特例】取a1=1,则易知数列前若干项为:1,2,4,3,7,5,9,…
该序列各项之间似乎没有什么联系,但这些项却有一个共同点,你发现了吗?
【发掘规律】这些数都只含有一个质因数,为pα形式的数。
它启发我们产生这样的设想:先证明只含有一个质因数的正整数pα都属于W,进而证明含有多个质因数的正整数也属于W(数列{an}各项组成的集合),由 此想到对正整数的质因数个数进行归纳。
【属性分批归纳】对正整数含有质因数的个数τ进行归纳。
当τ=1时,正整数为pα形式。
要证明pα∈W,需验证pα满足如下2个条件:
(1)存在正整数N,使(pα,SN)=1;
(2)pα是满足(1)且异于a1,a2,…,aN的最小正整数。
其中异于a1,a2,…,aN是可忽略的,否则pα∈{a1,a2,…,aN},当然有pα∈W。
但数列{an}及pα都不是具体的数,难以从正面找到合乎(1)(2)的N。宜从反面入手。
【反面思考】假定pαW,我们要导出与数列{an}的递归定义(1)(2)相矛盾。
容易发现,如果pα具有这两个性质,即(pα,SN)=1,且pα< aN+1,则与aN+1的最小性矛盾(pα更小),由此便找到了导出矛盾的大方向。
【性质分解】显然,要使pα< aN+1是很容易的,因为不超过pα的正整数只有有限个,数列{an}从某项起都会大于pα。不妨设pα< aN+1,则(pα,SN)≠1,即p|SN。
类似可知,(pα,SN+1)≠1,p|SN+1。
但(SN+1,SN)=(SN+1-SN,SN)=(aN+1,SN)=1,矛盾。
所以,τ=1时结论成立。
设τ<k(k≥2)时结论成立,考察τ=k的情形。
与τ=1时类似,难以从正面证明相应的正整数属于W,宜从反面入手。
【反面思考】假定存在正整数x=p1α1p2α2…pkαkW,我们要导出与数列{an}的递归定义(1)(2)相矛盾。
容易发现,如果x具有这两个性质,即(x,SN)=1,且x< aN+1,则与aN+1的最小性矛盾(xW当然异于a1,a2,…,aN,但x更小),由此便找到了导出矛盾的大方向。
【性质分解】同样,可取适当的N,使x< aN+1,则(x,SN)≠1,即存在1≤i≤k,使pi|SN。
类似可知,对任何n≥N,存在1≤i≤k,使pi|Sn。
注意到这里的pi有不同取值,与n相关,从而不能说明所有Sn(n>N)有公共质因数(n≥N)。
由此想到,我们需要找到一个公共的p=pi,及两个相邻的Sj、Sj-1,使p|Sj,p|Sj-1(j-1≥N)。(*)
这当然要利用归纳假设:正整数y=p1β1p2β2…pk-1βk-1属于W。
【建立联系】由于y不含质因数pk,想到我们要找到公共的p=pk,这只需存在j,使(y,Sj)=1,(y,Sj-1)=1(j-1≥N)。
其中(y,Sj-1)=1是很容易的,因为y∈W,可设y=aj,则由数列定义,(aj,Sj-1)=1,即(y,Sj-1)=1。
但此时未保证j-1≥N,需要优化假设。
【优化假设】为保证j-1≥N,只需y=aj异于a1,a2,…,aN,即j≠1,2,…,N,从而j>N。
为了使(*)成立,还必须x<aj,即y>x=p1α1p2α2…pkαk。
注意到βi可任意大,从而y=p1β1p2β2…pk-1βk-1可任意大,于是取y>x及y=aj异于a1,a2,…,aN都是可行的。
对于上述选定的y=aj,有(aj,Sj-1)=1(j-1≥N)。
进而也有(aj,Sj)=1。
实际上,(aj,Sj)=(aj,Sj-aj)=(aj,Sj-1)=1。
这说明Sj、Sj-1都不含质因数p1,p2,…,pk-1。
但x<aj,且x异于a1,a2,…,aj-1(因为x不属于W),所以(x,Sj-1)≠1(否则与aj的最小性矛盾,因为x比aj小),即存在1≤i≤k,使pi|Sj-1。
由于Sj-1不含质因数p1,p2,…,pk-1,只能是pk|Sj-1。
同样可知,pk|Sj。
但(Sj,Sj-1)=(Sj-Sj-1,Sj-1)=(aj,Sj-1)=1,矛盾。
【新写】设数列{an}各项组成的集合为W,我们证明任何正整数都属于W。对正整数所含质因数个数τ归纳。
当τ=1时,假定存在pαW,因为不超过pα的正整数只有有限个,必存在正整数N、N+1,使pα< aN+1,pα< aN+2。
易知(pα,SN)≠1,否则与aN+1的最小性矛盾,所以p|SN。同理,p|SN+1。
但(SN+1,SN)=(SN+1-SN,SN)=(aN+1,SN)=1,矛盾。
所以,τ=1时结论成立。
设τ<k(k≥2)时结论成立,考察τ=k的情形。
假定存在正整数x=p1α1p2α2…pkαkW,必存在正整数N,使n>N时,an>x。于是(Sn-1,x)≠1,否则与an的最小性矛盾(xW当然异于a1,a2,…,an-1,但x更小)。于是,存在1≤i≤k,使pi|Sn-1(∀n>N)。(*)
由归纳假设,可在W中取正整数aj=p1β1p2β2…pk-1βk-1,使aj异于a1,a2,…,aN(即j>N),且aj>x。
于是(aj,Sj-1)=1(j>N),否则与aj的最小性矛盾。
进而(aj,Sj)=(aj,Sj-aj)=(aj,Sj-1)=1。
但x<aj(j>N),由(*),存在1≤i≤k,使pi|Sj-1。
由于(aj,Sj-1)=1,只能是pk|Sj-1。同理,pk|Sj。
但(Sj,Sj-1)=(Sj-Sj-1,Sj-1)=(aj,Sj-1)=1,矛盾。
综上所述,命题获证。
联系客服