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)],结论成立。