組合構造第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都是"蒙人"的。