2018联赛加试压轴题（组合数论）思路分析

【附】为便于编辑修改，特提供纯文本文档如下：

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，矛盾。

综上所述，命题获证。