歡迎來到裝配圖網(wǎng)! | 幫助中心 裝配圖網(wǎng)zhuangpeitu.com!
裝配圖網(wǎng)
ImageVerifierCode 換一換
首頁 裝配圖網(wǎng) > 資源分類 > DOC文檔下載  

2019-2020年高中數(shù)學(xué)競賽教材講義 第十八章 組合.doc

  • 資源ID:2618668       資源大?。?span id="0fve3iq" class="font-tahoma">59KB        全文頁數(shù):3頁
  • 資源格式: DOC        下載積分:9.9積分
快捷下載 游客一鍵下載
會員登錄下載
微信登錄下載
三方登錄下載: 微信開放平臺登錄 支付寶登錄   QQ登錄   微博登錄  
二維碼
微信掃一掃登錄
下載資源需要9.9積分
郵箱/手機:
溫馨提示:
用戶名和密碼都是您填寫的郵箱或者手機號,方便查詢和重復(fù)下載(系統(tǒng)自動生成)
支付方式: 支付寶    微信支付   
驗證碼:   換一換

 
賬號:
密碼:
驗證碼:   換一換
  忘記密碼?
    
友情提示
2、PDF文件下載后,可能會被瀏覽器默認(rèn)打開,此種情況可以點擊瀏覽器菜單,保存網(wǎng)頁到桌面,就可以正常下載了。
3、本站不支持迅雷下載,請使用電腦自帶的IE瀏覽器,或者360瀏覽器、谷歌瀏覽器下載即可。
4、本站資源下載后的文檔和圖紙-無水印,預(yù)覽文檔經(jīng)過壓縮,下載后原文更清晰。
5、試題試卷類文檔,如果標(biāo)題沒有明確說明有答案則都視為沒有答案,請知曉。

2019-2020年高中數(shù)學(xué)競賽教材講義 第十八章 組合.doc

2019-2020年高中數(shù)學(xué)競賽教材講義 第十八章 組合一、方法與例題1抽屜原理。例1 設(shè)整數(shù)n4,a1,a2,an是區(qū)間(0,2n)內(nèi)n個不同的整數(shù),證明:存在集合a1,a2,an的一個子集,它的所有元素之和能被2n整除。證明 (1)若na1,a2,an,則n個不同的數(shù)屬于n-1個集合1,2n-1,2,2n-2,n-1,n+1。由抽屜原理知其中必存在兩個數(shù)ai,aj(ij)屬于同一集合,從而ai+aj=2n被2n整除;(2)若na1,a2,an,不妨設(shè)an=n,從a1,a2,an-1(n-13)中任意取3個數(shù)ai, aj, ak(ai,<aj< ak),則aj-ai與ak-ai中至少有一個不被n整除,否則ak-ai=(ak-aj)+(aj-ai)2n,這與ak(0,2n)矛盾,故a1,a2,an-1中必有兩個數(shù)之差不被n整除;不妨設(shè)a1與a2之差(a2-a1>0)不被n整除,考慮n個數(shù)a1,a2,a1+a2,a1+a2+a3,a1+a2+an-1。)若這n個數(shù)中有一個被n整除,設(shè)此數(shù)等于kn,若k為偶數(shù),則結(jié)論成立;若k為奇數(shù),則加上an=n知結(jié)論成立。)若這n個數(shù)中沒有一個被n整除,則它們除以n的余數(shù)只能取1,2,n-1這n-1個值,由抽屜原理知其中必有兩個數(shù)除以n的余數(shù)相同,它們之差被n整除,而a2-a1不被n整除,故這個差必為ai, aj, ak-1中若干個數(shù)之和,同)可知結(jié)論成立。2極端原理。例2 在nn的方格表的每個小方格內(nèi)寫有一個非負(fù)整數(shù),并且在某一行和某一列的交叉點處如果寫有0,那么該行與該列所填的所有數(shù)之和不小于n。證明:表中所有數(shù)之和不小于。證明 計算各行的和、各列的和,這2n個和中必有最小的,不妨設(shè)第m行的和最小,記和為k,則該行中至少有n-k個0,這n-k個0所在的各列的和都不小于n-k,從而這n-k列的數(shù)的總和不小于(n-k)2,其余各列的數(shù)的總和不小于k2,從而表中所有數(shù)的總和不小于(n-k)2+k23.不變量原理。俗話說,變化的是現(xiàn)象,不變的是本質(zhì),某一事情反復(fù)地進行,尋找不變量是一種策略。例3 設(shè)正整數(shù)n是奇數(shù),在黑板上寫下數(shù)1,2,2n,然后取其中任意兩個數(shù)a,b,擦去這兩個數(shù),并寫上|a-b|。證明:最后留下的是一個奇數(shù)。證明 設(shè)S是黑板上所有數(shù)的和,開始時和數(shù)是S=1+2+2n=n(2n+1),這是一個奇數(shù),因為|a-b|與a+b有相同的奇偶性,故整個變化過程中S的奇偶性不變,故最后結(jié)果為奇數(shù)。例4 數(shù)a1, a2,an中每一個是1或-1,并且有S=a1a2a3a4+ a2a3a4a5+ana1a2a3=0. 證明:4|n.證明 如果把a1, a2,an中任意一個ai換成-ai,因為有4個循環(huán)相鄰的項都改變符號,S模4并不改變,開始時S=0,即S0,即S0(mod4)。經(jīng)有限次變號可將每個ai都變成1,而始終有S0(mod4),從而有n0(mod4),所以4|n。4構(gòu)造法。例5 是否存在一個無窮正整數(shù)數(shù)列a1,<a2<a3<,使得對任意整數(shù)A,數(shù)列中僅有有限個素數(shù)。證明 存在。取an=(n!)3即可。當(dāng)A=0時,an中沒有素數(shù);當(dāng)|A|2時,若n|A|,則an+A均為|A|的倍數(shù)且大于|A|,不可能為素數(shù);當(dāng)A=1時,an1=(n!1)(n!)2n!+1,當(dāng)3時均為合數(shù)。從而當(dāng)A為整數(shù)時,(n!)3+A中只有有限個素數(shù)。例6 一個多面體共有偶數(shù)條棱,試證:可以在它的每條棱上標(biāo)上一個箭頭,使得對每個頂點,指向它的箭頭數(shù)目是偶數(shù)。證明 首先任意給每條棱一個箭頭,如果此時對每個頂點,指向它的箭頭數(shù)均為偶數(shù),則命題成立。若有某個頂點A,指向它的箭頭數(shù)為奇數(shù),則必存在另一個頂點B,指向它的箭頭數(shù)也為奇數(shù)(因為棱總數(shù)為偶數(shù)),對于頂點A與B,總有一條由棱組成的“路徑”連結(jié)它們,對該路徑上的每條棱,改變它們箭頭的方向,于是對于該路徑上除A,B外的每個頂點,指向它的箭頭數(shù)的奇偶性不變,而對頂點A,B,指向它的箭頭數(shù)變成了偶數(shù)。如果這時仍有頂點,指向它的箭頭數(shù)為奇數(shù),那么重復(fù)上述做法,又可以減少兩個這樣的頂點,由于多面體頂點數(shù)有限,經(jīng)過有限次調(diào)整,總能使和是對每個頂點,指向它的箭頭數(shù)為偶數(shù)。命題成立。5染色法。例7 能否在55方格表內(nèi)找到一條線路,它由某格中心出發(fā),經(jīng)過每個方格恰好一次,再回到出發(fā)點,并且途中不經(jīng)過任何方格的頂點?解 不可能。將方格表黑白相間染色,不妨設(shè)黑格為13個,白格為12個,如果能實現(xiàn),因黑白格交替出現(xiàn),黑白格數(shù)目應(yīng)相等,得出矛盾,故不可能。6凸包的使用。給定平面點集A,能蓋住A的最小的凸圖形,稱為A的凸包。例8 試證:任何不自交的五邊形都位于它的某條邊的同一側(cè)。證明 五邊形的凸五包是凸五邊形、凸四邊形或者是三角形,凸包的頂點中至少有3點是原五邊形的頂點。五邊形共有5個頂點,故3個頂點中必有兩點是相鄰頂點。連結(jié)這兩點的邊即為所求。7賦值方法。例9 由22的方格紙去掉一個方格余下的圖形稱為拐形,用這種拐形去覆蓋57的方格板,每個拐形恰覆蓋3個方格,可以重疊但不能超出方格板的邊界,問:能否使方格板上每個方格被覆蓋的層數(shù)都相同?說明理由。解 將57方格板的每一個小方格內(nèi)填寫數(shù)-2和1。如圖18-1所示,每個拐形覆蓋的三個數(shù)之和為非負(fù)。因而無論用多少個拐形覆蓋多少次,蓋住的所有數(shù)字之和都是非負(fù)的。另一方面,方格板上數(shù)字的總和為12(-2)+231=-1,當(dāng)被覆蓋K層時,蓋住的數(shù)字之和等于-K,這表明不存在滿足題中要求的覆蓋。-21-21-21-21111111-21-21-21-21111111-21-21-21-28圖論方法。例10 生產(chǎn)由六種顏色的紗線織成的雙色布,在所生產(chǎn)的雙色布中,每種顏色的紗線至少與其他三種顏色的紗線搭配過。證明:可以挑出三種不同的雙色布,它們包含所有的顏色。證明 用點A1,A2,A3,A4,A5,A6表示六種顏色,若兩種顏色的線搭配過,則在相應(yīng)的兩點之間連一條邊。由已知,每個頂點至少連出三條邊。命題等價于由這些邊和點構(gòu)成的圖中有三條邊兩兩不相鄰(即無公共頂點)。因為每個頂點的次數(shù)3,所以可以找到兩條邊不相鄰,設(shè)為A1A2,A3A4。(1)若A5與A6連有一條邊,則A1A2,A3A4,A5A6對應(yīng)的三種雙色布滿足要求。(2)若A5與A6之間沒有邊相連,不妨設(shè)A5和A1相連,A2與A3相連,若A4和A6相連,則A1A2,A3A4,A5A6對應(yīng)的雙色布滿足要求;若A4與A6不相連,則A6與A1相連,A2與A3相連,A1A5,A2A6,A3A4對應(yīng)的雙色布滿足要求。綜上,命題得證。二、習(xí)題精選1藥房里有若干種藥,其中一部分藥是烈性的。藥劑師用這些藥配成68副藥方,每副藥方中恰有5種藥,其中至少有一種是烈性的,并且使得任選3種藥恰有一副藥方包含它們。試問:全部藥方中是否一定有一副藥方至少含有4種烈性藥?(證明或否定)221個女孩和21個男孩參加一次數(shù)學(xué)競賽,(1)每一個參賽者最多解出6道題;(2)對每一個女孩和每一個男孩至少有一道題被這一對孩子都解出。求證:有一道題至少有3個女孩和至少有3個男孩都解出。3求證:存在無窮多個正整數(shù)n,使得可將3n個數(shù)1, 2, 3n排成數(shù)表a1, a2anb1, b2bnc1, c2cn滿足:(1)a1+b1+c1= a2+b2+c2= an+bn+cn=,且為6的倍數(shù)。(2)a1+a2+an= b1+b2+bn= c1+c2+cn=,且為6的倍數(shù)。4給定正整數(shù)n,已知克數(shù)都是正整數(shù)的k塊砝碼和一臺天平可以稱出質(zhì)量為1,2,n克的所有物品,求k的最小值f(n)。5空間中有1989個點,其中任何3點都不共線,把它們分成點數(shù)各不相同的30組,在任何3個不同的組中各取一點為頂點作三角形。試問:為使這種三角形的總數(shù)最大,各組的點數(shù)應(yīng)分別為多少?6在平面給定點A0和n個向量a1,a2,an,且使a1+a2+an =0。這組向量的每一個排列都定義一個點集:A1,A2,An=A0,使得求證:存在一個排列,使由它定義的所有點A1,A2,An-1都在以A0為角頂?shù)哪硞€600角的內(nèi)部和邊上。7設(shè)m, n, kN,有4個酒杯,容量分別為m,n,k和m+n+k升,允許進行如下操作:將一個杯中的酒倒入另一杯中或者將另一杯倒?jié)M為止。開始時,大杯中裝滿酒而另3個杯子卻空著,問:為使對任何SN,S<m+n+k,都可經(jīng)過若干次操作,使得某個杯子中恰有S升酒的關(guān)于m,n,k的充分必要條件是什么?8設(shè)有30個人坐在一張圓桌的周圍,其中的每個人都或者是白癡,或者是聰明人。對在座的每個人都提問:“你右邊的鄰座是聰明人還是白癡?”聰明人總是給出正確的答案,而白癡既可能回答正確,也可能回答不正確。已知白癡的個數(shù)不超過F,求總可以指出一位聰明人的最大的F。9某班共有30名學(xué)生,每名學(xué)生在班內(nèi)都有同樣多的朋友,期末時任何兩人的成績都可分出優(yōu)劣,沒有相同的。問:比自己的多半朋友的成績都要好的學(xué)生最多能有多少人?

注意事項

本文(2019-2020年高中數(shù)學(xué)競賽教材講義 第十八章 組合.doc)為本站會員(tia****nde)主動上傳,裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對上載內(nèi)容本身不做任何修改或編輯。 若此文所含內(nèi)容侵犯了您的版權(quán)或隱私,請立即通知裝配圖網(wǎng)(點擊聯(lián)系客服),我們立即給予刪除!

溫馨提示:如果因為網(wǎng)速或其他原因下載失敗請重新下載,重復(fù)下載不扣分。




關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號:ICP2024067431-1 川公網(wǎng)安備51140202000466號


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請立即通知裝配圖網(wǎng),我們立即給予刪除!