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

《2019-2020年高中數(shù)學(xué)競(jìng)賽輔導(dǎo)資料《組合數(shù)學(xué)選講》.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《2019-2020年高中數(shù)學(xué)競(jìng)賽輔導(dǎo)資料《組合數(shù)學(xué)選講》.doc（6頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

2019-2020年高中數(shù)學(xué)競(jìng)賽輔導(dǎo)資料《組合數(shù)學(xué)選講》 組合數(shù)學(xué)是中學(xué)數(shù)學(xué)競(jìng)賽的“重頭戲”，具有形式多樣，內(nèi)容廣泛的特點(diǎn).本講主要圍繞組合計(jì)數(shù)，組合恒等式及組合最值展開(kāi) 例題講解 1．圓周上有800個(gè)點(diǎn)，依順時(shí)針?lè)较驑?biāo)號(hào)為1,2,…,800它們將圓周分成800個(gè)間隙.今選定某一點(diǎn)染成紅色，然后按如下規(guī)則，逐次染紅其余的一些點(diǎn)：若第k號(hào)點(diǎn)染成了紅色，則可依順時(shí)針?lè)较蜣D(zhuǎn)過(guò)k個(gè)間隙，將所到達(dá)的點(diǎn)染成紅色，試求圓周上最多可以得到多少個(gè)紅點(diǎn)？ 2．集合X的覆蓋是指X的一族互不相同的非空子集A1、A2、…、Ak，它們的并集A1∪A2∪…∪Ak =X，現(xiàn)有集合X={1,2,…,n}，若不考慮A1, A2,…, Ak的順序，試求X的覆蓋有多少個(gè)？ 3．已知集合X={1,2,…,n}，映射f：X→X，滿足對(duì)所有的x∈X，均有f(f(x))=x，求這樣的映射f的個(gè)數(shù). 4．S為{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，我們稱(chēng)距離為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．解：易見(jiàn)，第k號(hào)點(diǎn)能被染紅的充要條件是 $jN*{0}，使得a02jk (mod800)，1≤k≤800 ① 這里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)j≥5時(shí) 2j+20-2j=2j(220-1)0(mod 800), 而對(duì)"k<20,kN*，及j≥5,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è)；依次類(lèi)推，則由容斥原理，X的覆蓋共有 =個(gè). 注：有些組合計(jì)數(shù)問(wèn)題直接計(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ù)問(wèn)題，以多次在國(guó)際競(jìng)賽中出現(xiàn)，但對(duì)于一般地情況(f(n)(x)=x)下的映射計(jì)數(shù)，尚無(wú)較好的結(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)(1≤i≤n)，2為公比的等比數(shù)列與A的交集記為A. 一方面，由于M中的2mn-n個(gè)元的子集{n+1,n+2,…,2mn}中，若存在滿足要求的m+1個(gè)數(shù)：n+1≤a12mn，矛盾，故不存在滿足要求的m+1個(gè)數(shù)，因此所求的k≥2mn-n+1. 另一方面，若k=2mn-n+1時(shí)，可證明M中的任何k元子集T中，此有m+1個(gè)數(shù)a1,a2,…am+1滿足ai|ai+1 (i≤1≤m). 反證：假設(shè)這樣的m+1個(gè)數(shù)不存在，考慮2i+1為首項(xiàng)，2為公比的等比數(shù)列，它與集合M的交的元素個(gè)數(shù)為|A2i+1|+m，由假設(shè)知，它至少有|A2i+1|個(gè)元素不在T中，再注意到當(dāng)i≠j時(shí)，A2i+1A2j+1=f，可知M中至少有個(gè)元素不在T中， 注意到 所以 ， 從而 |T|≤|M|-n≤2mn-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ù)法，是證明組合問(wèn)題重要方法之一，但如何找到母函數(shù)，是需要長(zhǎng)時(shí)間的體驗(yàn)的. A C B D 8．證明：[引理]：平面上n(n≥3)個(gè)點(diǎn)所組成的點(diǎn)集S中，或者存一點(diǎn)至多能引出一條直徑，或者任一點(diǎn)至多能引出兩條直徑. [引理的證明]：若每一點(diǎn)都至少能引出兩條直徑，又有一點(diǎn)A能引出三條直徑AB、AC、AD，則不妨設(shè)AD在AB與AC之間，且必須BAC≤60o，因此⊙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ì)一般的圖形也可定義直徑、半徑等.本問(wèn)題還可推廣至三維空間. 9．證明：必要性： 構(gòu)造母函數(shù)， . 所以 ， 所以 ，即. 因?yàn)?，所以. 所以 存在，使得 ， 所以 ， 所以 ， 所以 . 令x=1,則，所以，，即n為2的冪次. 充分性：直接構(gòu)造如下 中取個(gè)，其中 ，中取個(gè) ,其中，則這兩個(gè)集合滿足要求. 注：運(yùn)用母函數(shù)處理集合問(wèn)題，是常見(jiàn)的方法，尤其注意這種集合中出現(xiàn)在指數(shù)上而不是系數(shù)上的母函數(shù)方法.