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≤a1- 1.請仔細(xì)閱讀文檔,確保文檔完整性,對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請點此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標(biāo),表示該PPT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 組合數(shù)學(xué)選講 2019 2020 年高 數(shù)學(xué) 競賽 輔導(dǎo)資料 組合
鏈接地址:http://www.3dchina-expo.com/p-2480399.html