圓周上有800個點，依順時針方向標(biāo)號為1,2,…,800它們將圓周分成800個間隙.今選定k個間隙，將所到達的點染成紅色，試求圓周上最多可以得到多少個紅點？XXA1、A2、…、Ak∪AkXX={1,2,…,n}A1A2,…AkX的個數(shù)nn(Sperner定理 M1,2,3,…,2mn}(m,nN*)2mnk，使得M的任何k集中都存在m+1個數(shù)，a1,a2,…am+1，滿足ai|ai+1(i=1,2,…,m). 2n計算k

kkqq

n

mmn

kqk k0 n(≥3)dd的兩點間的n條.9．已知：兩個非負整數(shù)組成的不同集合{a1aa,an{b1b2,bn}求證：集合{aiaj1i

jn與集合{bibj1i

jnn2集合內(nèi)，相同的元素重復(fù)出現(xiàn)課后練nn

2nkkk0

n n kn

1

1 11的兩點2例題答案kjN*{0}，使得a02jk a0a0=1.2jkj=0,1,2,3,4時，k1,2,4,8,16225的階25(220j≥52j+202j=2j(2201)0(mod2j+k2j=2j(2k1)800的倍數(shù).5+20=25k注：本題解法不止一種，但利用些同余理論，可使解法簡潔許多解：首先，X2n1個，它們共組成了22n1-1個非空子集族.其次，這些子集族中，不合某一元素i的非空子集組成的非空子集族有22n111個；不含兩個元素的子集組的族有22n211個；依次類推，則由容斥原理，X的覆蓋共n2n1 nn

2n11 n

2n21

(1)jn(22n11

1

2

個j注：有些組合計數(shù)問題直接計數(shù)較難，但從考慮簡潔明了解：設(shè)njx、yf(x)=yf(y)=xf(x)=x，則j=0時，僅一種映射，即恒等映射.nn2 n2j2j>0j對有2

2

種取法j1nn2 n2j2 n

j!2

2

2j(2j1)!! 2jn2j因此，映射f的個數(shù)為1 (2j1)!!j1 n1,2,…,nn!k個元素恰SSik!(nk)!SS中的全排列互不同SfkAi，滿足|Ai|=kk=1,2,…,n) n

nfkk!(nkn!,又然知k在k2k 當(dāng)S是由{1,2,…,n}中全部 集組成時，等號成立

注：Sperner1928年發(fā)現(xiàn)，證明的方法不止一種M2mnn個元的子集{n+1,n+2,…,2mn}m+1n+1≤a1<a2<…<am+1≤2mn，使得ai|ai+1(1≤i≤m)，則ai+1≥2ai，從而am+1≥2am≥…≥2ma1≥2m(n+1)>2mn，，故不存在滿足要求的m+1個數(shù)，因此所求的k≥2mnn+1.另一方面，若k=2mnn+1時，可證明M中的任何k集T中，此有m+1個數(shù)ai|ai+1m+12i+1為首項in1，2 2 M的交的元素個數(shù)為|A2i+1|+m，由假設(shè)知，它至少有|A2i+1|Ti≠j時，A2i+1A2j+1=M

1in-2

|A2i+1|T

A2i11in2

所以|MS

|nA2i+1|1in2從而|T|≤|M|A2i+1|1in2kk k nn

2n

2nn

kk k

k1 nkn1kn1n

k

k

l

ln=ln1kn1n=lk

lnnl=lk

ln12n1再次用nnn1，所以ln12n1ln1n2 ,k kk

l

l

ll=(n1)n22nlllll作指標(biāo)變換，令l1=Sn1lsn2 l

l

2n

(n1)2n22n1 所以k

n(nkk

n

n(n 注：用利基本的組合恒等式及指標(biāo)變換，是證明組合恒等式的重要方法之一nm證明：, 因為的母函數(shù)分別為(1+x)n和kkqnm q而 是這兩個母函數(shù)(1+x)m(1+x)n=(1+x)m+n中xq項的系數(shù)，又由于(1+x)m+n qk0 mn系數(shù)為 ，因此命題成立 驗的

證明：[引理]n(n≥3)SCACA··BAB、AC、ADADABACS，顯然與D能引出兩條直徑，!引理得證(如圖).下用歸納法證kSk+12(kS2

k1條直徑，從而命題成立f(x)xa1xa2xang(x)xb1xb2xbn所以f2xf(x2

xaiaj，g2(x)g(x2)

xbi1i 1i所以f2xf(x2g2xg(x2f2xg2x)f(x2g(x2因為f(1g(1)0x1f(xg(x所以存在hN

(x1)hP(x)

f(x)g(x),P(x)0所以f2xf(x2(x21)hP(x2所以f(xg(x)](x1)hP(x)(x21)hP(x2所以f(x