组合构造第1章:容易求值4


【附】为便于有需要者编辑修改,特提供纯文本文档如下:

例6、给定自然数n,设X={1,2,3,…,n},A1,A2,…,Ar是X的r 个互不相交的三元子集,使得

(1)S(Ai)≤n(1≤i≤r),

(2)S(Ai)≠S(Ai)(1≤i<j≤r),

其中S(A)表示A中所有元素的和,求r的最大值。

分析与解:由划分的意义,有|Ai|=3r。

又各A i互不相交,所以S(Ai)=S(Ai)≥1+2+…+3r。

由条件(1)和(2),有 S(Ai)≤n+(n–1)+…+(n–r+1),

所以1+2+…+3r≤n+(n–1)+…+(n–r+1),解得r≤(n–1)。

注意到 r∈N,所以r≤[(n–1)]。

若r=[(n–1)],我们可构造合乎条件的r个三元子集。为了满足条件:S(Ai)≤n,应取尽可能小的元素属于Ai,尝试令Ai={1,2,…,3r}进行构造。为了满足条件:

S(Ai)≠S(Aj),从容易计算的角度考虑,可想象{ S(Ai)}是公差为1的等差数列。这样,我们只需先将1,2,…,2r分为r个集合,使其和相等,这利用“大小搭配”是很易作到的。最后将2r+1,2r+2,2r+3,…,3r分配到每个集合中,每个集合中分配一个元素即可。比如,令Ai={i,2r+i,2r–i+1}(i=1,2,…,r),则各个集合的和不相等,且最大的和为5r+1≤(n–1)+1=n。

故r的最大值为[(n–1)]。


例7、求证:对任何0<a<b,存在正整数k及n1,n2,…,nk,使a<++…+<b。

分析与解: 首先,为了使++…+易于估计,注意到级数是发散,想到寻找连续的自然数n,n+1,n+2,…,n+k,使不等式(*)成立。由的发散性,可先找到k,使>a成立(即不等式的左端成立)。为了使不等式右端也成立,应使尽可能小,于是取k是满足>a的最小的k,即>a,而≤a。这样, a<=+≤a+。

我们期望 a+<b,一个充分条件是a+<b,即 n>。

但a<≤,所以n>。

综上可知,取n>max{, },不等式获证。

注: 取a=33–π–1959,b=33–π–1992,则得到33备选题:存在自然数k及互异的自然数:n1,n2,…,nk,使π–1992<33–(++…+)<π–1959。由本题可知,题中的常数33,π–1992,π–1959都是"蒙人"的。