2019-2020年高中數(shù)學(xué)競(jìng)賽輔導(dǎo)資料《組合數(shù)學(xué)選講》.doc

2019-2020年高中數(shù)學(xué)競(jìng)賽輔導(dǎo)資料組合數(shù)學(xué)選講組合數(shù)學(xué)是中學(xué)數(shù)學(xué)競(jìng)賽的“重頭戲”，具有形式多樣，內(nèi)容廣泛的特點(diǎn).本講主要圍繞組合計(jì)數(shù)，組合恒等式及組合最值展開例題講解1圓周上有800個(gè)點(diǎn)，依順時(shí)針方向標(biāo)號(hào)為1,2,800它們將圓周分成800個(gè)間隙.今選定某一點(diǎn)染成紅色，然后按如下規(guī)則，逐次染紅其余的一些點(diǎn)：若第k號(hào)點(diǎn)染成了紅色，則可依順時(shí)針方向轉(zhuǎn)過k個(gè)間隙，將所到達(dá)的點(diǎn)染成紅色，試求圓周上最多可以得到多少個(gè)紅點(diǎn)？2集合X的覆蓋是指X的一族互不相同的非空子集A1、A2、Ak，它們的并集A1A2Ak =X，現(xiàn)有集合X=1,2,n，若不考慮A1, A2, Ak的順序，試求X的覆蓋有多少個(gè)？3已知集合X=1,2,n，映射f：XX，滿足對(duì)所有的xX，均有f(f(x)=x，求這樣的映射f的個(gè)數(shù).4S為1,2,n的一些子集族，且S中任意兩個(gè)集合互不包含，求證：S的元素個(gè)數(shù)的最大值為(Sperner定理)5設(shè)M= 1,2,3,2mn (m,nN*)是連續(xù)2mn個(gè)正整數(shù)組成的集合，求最小的正整數(shù)k，使得M的任何k元子集中都存在m+1個(gè)數(shù)，a1,a2,am+1，滿足ai|ai+1 (i=1,2,m).6計(jì)算.7證明： (范德蒙公式)8在平面上有n(3)個(gè)點(diǎn)，設(shè)其中任意兩點(diǎn)的距離的最大值為d，我們稱距離為d的兩點(diǎn)間的線段為該點(diǎn)集的直徑，證明：直徑的數(shù)目至多有n條.9已知：兩個(gè)非負(fù)整數(shù)組成的不同集合和.求證：集合與集合相同的充要條件是n是2的冪次，這里允許集合內(nèi)，相同的元素重復(fù)出現(xiàn).課后練習(xí)1. 空間n條直線，最多能把空間分成多少塊空間區(qū)域？2. 證明：.3. 證明：.4. 證明：在邊長(zhǎng)為1的等邊三角形內(nèi)有五個(gè)點(diǎn)，則這五個(gè)點(diǎn)中一定有距離小于的兩點(diǎn).例題答案：1解：易見，第k號(hào)點(diǎn)能被染紅的充要條件是 $jN*0，使得a02jk (mod800)，1k800 這里a0是最初染的點(diǎn)的號(hào)碼，為求最大值，不妨令a0=1.即2jk (mod2552).當(dāng)j=0,1,2,3,4時(shí)，k分別為1,2,4,8,16，又由于2模25的階，因此，當(dāng)j5時(shí)2j+20-2j=2j(220-1)0(mod 800),而對(duì)"k<20,kN*，及j5,jN*，由于25+(2k-1)，所以2j+k-2j=2j(2k-1)不為800的倍數(shù).所以，共存在5+20=25個(gè)k，滿足式。注：本題解法不止一種，但利用些同余理論，可使解法簡(jiǎn)潔許多.2解：首先，X的非空子集共有2n-1個(gè)，它們共組成了-1個(gè)非空子集族.其次，這些子集族中，不合某一元素i的非空子集組成的非空子集族有個(gè)；不含兩個(gè)元素的子集組成的族有個(gè)；依次類推，則由容斥原理，X的覆蓋共有=個(gè).注：有些組合計(jì)數(shù)問題直接計(jì)數(shù)較難，但從反面考慮簡(jiǎn)潔明了.3解：設(shè)n元中有j個(gè)對(duì)x、y滿足f(x)=y且f(y)=x，其余的滿足f(x)=x，則當(dāng)j=0時(shí)，僅一種映射，即恒等映射.當(dāng)j>0時(shí)，每次取兩個(gè)作為一對(duì)，共取j對(duì)有種取法.則不考慮j對(duì)的順序，有 .因此，映射f的個(gè)數(shù)為 .注：這些計(jì)數(shù)問題，以多次在國(guó)際競(jìng)賽中出現(xiàn)，但對(duì)于一般地情況(f(n)(x)=x)下的映射計(jì)數(shù)，尚無較好的結(jié)論.4解：考慮n個(gè)元素1,2,n的全排列，顯然為n!種，另一方面，全排列中前k個(gè)元素恰好組成S中的某個(gè)集Si的，有k!(n-k)!個(gè)，由于S中任意子集互不包含，所以，這種“頭”在S中的全排列互不同.設(shè)S中有fk個(gè)Ai，滿足|Ai|=k (k=1,2,n)，則,又然知在時(shí)最大，因此當(dāng)S是由1,2,n中全部元子集組成時(shí)，等號(hào)成立.注：Sperner定理是1928年發(fā)現(xiàn)，證明的方法不止一種.5解：記A=1,2,n，任何一個(gè)以i為首項(xiàng)(1in)，2為公比的等比數(shù)列與A的交集記為A.一方面，由于M中的2mn-n個(gè)元的子集n+1,n+2,2mn中，若存在滿足要求的m+1個(gè)數(shù)：n+1a1<a2<<am+12mn，使得ai|ai+1 (1im)，則ai+12ai，從而am+12am2ma12m(n+1)>2mn，矛盾，故不存在滿足要求的m+1個(gè)數(shù)，因此所求的k2mn-n+1.另一方面，若k=2mn-n+1時(shí)，可證明M中的任何k元子集T中，此有m+1個(gè)數(shù)a1,a2,am+1滿足ai|ai+1 (i1m).反證：假設(shè)這樣的m+1個(gè)數(shù)不存在，考慮2i+1為首項(xiàng)，2為公比的等比數(shù)列，它與集合M的交的元素個(gè)數(shù)為|A2i+1|+m，由假設(shè)知，它至少有|A2i+1|個(gè)元素不在T中，再注意到當(dāng)ij時(shí)，A2i+1A2j+1=f，可知M中至少有個(gè)元素不在T中，注意到 所以 ，從而 |T|M|-n2mn-n，這與|T|=2mn-n+1矛盾.故假設(shè)不成立.綜上所述滿足要求的最小正整數(shù)值k為2mn-n+1.注：這種先確定單邊界限再證明最值是經(jīng)常采用的.6.解：，作指標(biāo)變換，令=k-1，則，因此，, = , = .再次用，所以 , =, =.作指標(biāo)變換，令-1=S，則，所以 = .所以 .注：用利基本的組合恒等式及指標(biāo)變換，是證明組合恒等式的重要方法之一.7證明：因?yàn)榈哪负瘮?shù)分別為 (1+x)n和(1+x)m而是這兩個(gè)母函數(shù)(1+x)m(1+x)n=(1+x)m+n中xq項(xiàng)的系數(shù)，又由于(1+x)m+n中xq的系數(shù)為，因此命題成立.注：構(gòu)造母函數(shù)法，是證明組合問題重要方法之一，但如何找到母函數(shù)，是需要長(zhǎng)時(shí)間的體驗(yàn)的.A CBD8證明：引理：平面上n(n3)個(gè)點(diǎn)所組成的點(diǎn)集S中，或者存一點(diǎn)至多能引出一條直徑，或者任一點(diǎn)至多能引出兩條直徑.引理的證明：若每一點(diǎn)都至少能引出兩條直徑，又有一點(diǎn)A能引出三條直徑AB、AC、AD，則不妨設(shè)AD在AB與AC之間，且必須BAC60o，因此A(d)、B(d)、C(d)的公共部分覆蓋了整個(gè)點(diǎn)集S，顯然與D能引出兩條直徑，矛盾!引理得證(如圖).下用歸納法證明原體：顯然，當(dāng)n=3時(shí)，命題成立，假設(shè)命題對(duì)k個(gè)點(diǎn)成立，則當(dāng)n=k+1時(shí)，如有一點(diǎn)A至多能引出一條直徑，去掉A點(diǎn)后，至多還有k條直徑，故S最多有k+1條直徑，否則任一點(diǎn)至多能引出兩條直徑，故S最多有條直徑，從而命題成立.注：組合幾何在研究點(diǎn)集的組合性質(zhì)時(shí)，對(duì)一般的圖形也可定義直徑、半徑等.本問題還可推廣至三維空間.9證明：必要性： 構(gòu)造母函數(shù)，.所以 ，所以 ，即.因?yàn)?，所以.所以 存在，使得 ，所以 ，所以 ，所以 .令x=1,則，所以，即n為2的冪次.充分性：直接構(gòu)造如下中取個(gè)，其中 ，中取個(gè),其中，則這兩個(gè)集合滿足要求.注：運(yùn)用母函數(shù)處理集合問題，是常見的方法，尤其注意這種集合中出現(xiàn)在指數(shù)上而不是系數(shù)上的母函數(shù)方法.