2019-2020年高中數學競賽輔導資料《組合數學選講》.doc

《2019-2020年高中數學競賽輔導資料《組合數學選講》.doc》由會員分享，可在線閱讀，更多相關《2019-2020年高中數學競賽輔導資料《組合數學選講》.doc（6頁珍藏版）》請在裝配圖網上搜索。

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