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

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

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