2018联赛加试第3题（组合数论）分析与解答
【附】为便于编辑修改，特提供纯文本文档如下：
2018联赛加试第3题（组合数论）思路分析
冯跃峰
2018年全国高中数学联赛加试第3题是一道比较新颖的组合数论题，颇为有趣：要证明的是集合A的“自差集”覆盖（0，n/（k-1））中的所有整数。它含有一定的数论知识背景以及不等式证明中的放缩变形技巧，组合的味道并不很浓。
下面是我们对该题解答的思路分析。
【题目】设n、k、m是正整数，满足k≥2，且n≤m<（2k-1）n/k。设A是{1，2，…，m}的n元子集，试证：区间（0，n/（k-1））中的每个整数均可表示为a-a'，其中a、a'∈A。（2018高中数学联赛加试第3题）
【题感】从目标看，要证“（0，n/（k-1））中的每个整数均可表成A中两数之差”（简称“可由A表出”），这属于“全范围型”问题，一般的做法是取一个“代表”来论证：任取整数d∈（0，n/（k-1）），证明d可由A表出。
但题中含有较多的参数，比较抽象，给解题造成困难。再加入一个抽象的字母d，一时不知从何处着手。因此，不妨从一些具体整数入手，依次考察1，2，…怎样由A表出，探索解题方向。
【穷举试验】先证（0，n/（k-1））中的整数1可由A表出。
因为A并不唯一，无法确定A中究竟含有哪些元素，因而无法从正面判断1可由A表出，宜从反面思考。
【反面思考】反设1不可由A表出，则A中不能含有相邻自然数。
这样的A具有怎样的特征呢？——{1，2，…，m }中属于A的元素的分布是比较稀疏的：任何相邻两个自然数中至多有一个属于A。
这自然想到“间距”估计，由此算出A中元素个数的上界，期望与题设条件产生矛盾。
【间距估计】因为1，2，…，m中每相邻两项至多一项属于A，所以n≤。
为了计算取整函数，对m分奇偶讨论。
如果m为奇数，则n≤（m+1）/2。
我们期望该不等式与题给条件矛盾。
由条件，有n>km/（2k-1），联立“消去”n，得km/（2k-1）<（m+1）/2，解得m<2k-1。
但m为奇数，所以m≤2k-3，进而n≤（m+1）/2≤k-1，这与1∈（0，n/（k-1））矛盾。
如果m为偶数，则n≤m/2。结合n>km/（2k-1），得km/（2k-1）< m/2，化简，得2k<2k-1，矛盾。
所以，1可由A表出。
【穷举试验】再证（0，n/（k-1））中的整数2可由A表出。
【反面思考】反设2不可由A表出，则A具有与上类似的“稀疏”特征：每个子列{1+2p}、{2+2q}（p、q∈N）中任何相邻两项至多有一个属于A。
进行类似“间距”估计，可得到A中元素个数的上界，进而与题设条件产生矛盾。显然，这一方法可直接迁移到一般情形。
【方法迁移】反设（0，n/（k-1））中的整数d不可由A表出，则将{1，2，…，m}划分为d子列：{i+pd（p∈N）}（1≤i≤d），每个子列中任何相邻两项至多有一个属于A。
【结构联想】为了准确估算每个子列的项数，将m用模d带余表示。
设m=qd+r（0≤r<d），则前r个子列有q+1项，后（d-r）个子列有q项。
【间距估计】每个子列任何相邻两项不同时属于A，所以
前r个子列都至多有个数属于A，后（d-r）个子列至多有个数属于A。所以n≤r+（d-r）。
为了计算取整函数，对q分奇偶讨论。
（1）如果q为奇数，则n≤r+（d-r）= d。
期望该不等式与题给条件矛盾。
由条件，有qd+r=m<（2k-1）n/k，得n>kqd/（2k-1），
所以kqd/（2k-1）< d解得q<2k-1。但q为奇数，所以q≤2k-3，进而n≤d≤（k-1）d，这与d∈（0，n/（k-1））矛盾矛盾。
（2）如果q为偶数，则n≤r+（d-r）= d+r。
又由qd+r =m<（2k-1）n/k，得n>k（qd+r）/（2k-1），
所以k（qd+r）/（2k-1）< d+r。
化简，得qd<（2k-2）r，所以q<（2k-2）≤2k-2。
但q为偶数，所以q≤2k-4，进而n≤d+r<（k-2）d+r≤（k-2）d+d=（k-1）d，这与d∈（0，n/（k-1））矛盾。
所以，d可由A表出，命题获证。
【新写】反设（0，n/（k-1））中的整数d不能表成A中两数之差，将{1，2，…，m}划分为d子列：{i+pd（p∈N）}（1≤i≤d），则各子列每相邻两项都至多有一项属于A。
设m=qd+r（0≤r<d），则前r个子列有q+1项，后（d-r）个子列有q个项，所以n≤r+（d-r）。
（1）如果q为奇数，则n≤d（q+1）/2。
由条件，qd+r=m<（2k-1）n/k，得n>kqd/（2k-1），所以kqd/（2k-1）< d（q+1）/2，解得q<2k-1。但q为奇数，所以q≤2k-3，进而n≤d（q+1）/2≤（k-1）d，这与d∈（0，n/（k-1））矛盾。
（2）如果q为偶数，则n≤dq/2+r。
又由qd+r =m<（2k-1）n/k，得n>k（qd+r）/（2k-1），所以k（qd+r）/（2k-1）< dq/2+r。化简得q<（2k-2）r/d≤2k-2。但q为偶数，所以q≤2k-4，进而n≤dq/2+r<（k-2）d+r≤（k-1）d，这与d∈（0，n/（k-1））矛盾。
综上所述，命题获证。
【注】若将m<（2k-1）n/k改为m≤（2k-1）n/k，则结论不再成立。反例如下：
取m=5，n=k=3，A={1，3，5}是X={1，2，3，4，5}的3元子集，但（0，n/（k-1））中的整数1不可表成A两数之差。
笔者对加试压轴题也写了一个类似的分析与解答，有兴趣的读者可参看相关文献。
2017高中数学联赛加试压轴题（组合数论）剖析
【注】为方便复制编辑，特提供纯文本如下：
2017高中数学联赛加试压轴题（组合数论）剖析
冯跃峰
2017年全国高中数学联赛加试压轴题是一道组合数论题，题目如下：
【题目】设m、n均是大于1的整数，m≥n，又a1，a2，…，an是n个不超过m的互不相同正整数，且（a1，a2，…，an）=1。试证：对任意实数x，均存在ai（1≤i≤n），使得||aix||≥2||x||/[m（m+1）]，这里||y||表示实数y到与它最近的整数的距离。
【题感】从目标看，属于“在多个数a1，a2，…，an中找一个数ai，使||aix||具有题给性质”的问题，这通常可用整体思考：考虑所有的||aix||（1≤i≤n），然后构造整体函数W=f（||a1x||，…，||anx||），通过研究W的性质找到相应的||aix||。
如何构造整体函数W（常见的是和或积）？这当然要利用题给条件，其中最主要的条件是（a1，a2，…，an）=1，它与整体函数密切相关。
由此想到裴蜀定理：p1a1+ p2a2+…+ pnan=1。所以选择整体函数为“和”的形式，这只需在上式中凑配||aix||。
【结构联想】因为（a1，a2，…，an）=1，由裴蜀定理，存在常数p1，p2，…，pn，使Σi=1npiai=1。
【构造相同】于是，对任意实数x，有Σi=1npiaix=x，所以
||Σi=1npiaix||=||x||……（*）
【瞄准目标】我们要证明：||x||≤[m（m+1）||aix||]/2……（**）
为了构造||aix||，想到（*）式左端的距离符号放入求和运算的每一项中，这就要研究对u、v∈R，||u+v||与||u||、||v||的关系。不难发现如下的
引理1：对u、v∈R，||u+v||≤||u||+||v||。
证明：因为对任何整数k及实数x，有||x+k||=||x||，所以不妨设-1/2≤u，v≤1/2。
又由定义||-x||=||x||，所以不妨设0≤u，v≤1/2，此时与u、v最近的整数都是0，所以||u||=u，||v||=v。
【充分条件分类】如果0≤u+v≤1/2，则将u+v看作一个数，有||u+v||=|u+v|=u+v=||u||+||v||，结论成立。
【解决遗留】如果u+v>1/2，由定义（将u+v看作一个数），||u+v||≤1/2，所以||u+v||≤1/2<u+v=||u||+||v||，结论成立，引理1获证。
由引理1可知，||Σi=1nui||≤Σi=1n||ui||。
再结合||-x||=||x||，对任何k∈Z，x∈R，有||kx||≤|k|·||x||。
于是，由（*）式，有
||x||=||Σi=1npiaix||≤Σi=1n||piaix||≤Σi=1n|pi|·||aix||。
注意目标式含有系数m，瞄准目标，期望|pi|≤m，由此想到裴蜀定理的结果可以优化：限定|pi|≤a=max{ a1，a2，…，an }≤m（1≤i≤n）。
引理2：如果（a1，a2，…，an）=1，则存在常数p1，p2，…，pn，使Σi=1npiai=1，且|pi|≤a=max{ a1，a2，…，an }。
证明：因为（a1，a2，…，an）=1，由裴蜀定理，存在常数p1，p2，…，pn，使Σi=1npiai=1。
【逐步调整】如果存在pi（1≤i≤n），使得|pi|>a，不妨设|p1|>a，且p1>0。
但Σi=1npiai=1，所以必存在pj（1≤j≤n），使得pj<0，不妨设p2<0。
在等式中添加（-a1a2+a1a2），有
1=p1a1+（-a1a2+a1a2）+p2a2+Σi=3npiai
=（p1-a2）a1+（p2+a1）a2 +Σi=3npiai=Σi=1npi'ai，
其中p1'= p1-a2， p2'= p2+a1，pi'=（3≤i≤n）。
经过一次调整，p1至少减少1，至多减少a，所以调整后p1仍大于0，且p2增加正数a1，其绝对值不增加。
于是，若干次调整后必定使p1的绝对值不大于a，且其他系数的绝对值不增加。
如此下去，可使所有系数的绝对值不大于a，引理2获证。
利用引理2，由前面的结果，得
||x||≤Σi=1n|pi|·||aix||≤Σi=1na·||aix||≤mΣi=1n||aix||。
于是，一定存在ai（1≤i≤n），使得||aix||≥||x||/mn。
【充分条件分类】如果n≤（m+1）/2，则||aix||≥||x||/mn≥2||x||/[m（m+1）]，结论成立。
【解决遗留】如果n>（m+1）/2，此时a1，a2，…，an具有怎样的性质？
——注意此时数很多，但都在区间[1，m]中，数的个数多于区间长度的一半，将出现怎样的现象？
此时a1，a2，…，an中必定有2个相邻自然数，设为a2-a1=1，此时只需考虑小范围的整体函数||a1x||+||a2x||即可！
实际上，由引理1，有||a1x||+||a2x||≥||a2x-a1x||=||x||，
不妨设||a1x||≥||a2x||，则||a1x||≥||x||/2≥2||x||/[m（m+1）]，结论成立。
【新写】先证明如下两个引理。
引理1：对u、v∈R，||u+v||≤||u||+||v||。（证明同上，略）
由引理1可知，||Σi=1nui||≤Σi=1n||ui||。
再结合||-x||=||x||，对任何k∈Z，x∈R，有||kx||≤|k|·||x||。
引理2：存在常数p1，p2，…，pn，使Σi=1npiai=1，且|pi|≤a=max{ a1，a2，…，an }。（证明同上，略）
解答原题：如果n>（m+1）/2，但a1，a2，…，an∈[1，m]中，必定有2个相邻自然数，设为a2-a1=1。由引理1，有||a1x||+||a2x||≥||a2x-a1x||=||x||，
不妨设||a1x||≥||a2x||，则||a1x||≥||x||/2≥2||x||/[m（m+1）]，结论成立。
如果n≤（m+1）/2，因为（a1，a2，…，an）=1，存在常数p1，p2，…，pn，使Σi=1npiai=1，且|pi|≤a=max{ a1，a2，…，an }。
于是，对任意实数x，有Σi=1npiaix=x，所以结合引理1，有
||x||≤Σi=1n|pi|·||aix||≤Σi=1na·||aix||≤mΣi=1n||aix||。
于是，一定存在ai（1≤i≤n），使得||aix||≥||x||/mn≥2||x||/[m（m+1）]，结论成立。
