版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、抽屜原理. 基礎(chǔ)知識(shí)回顧一、抽屜原理把八個(gè)蘋果任意地放進(jìn)七個(gè)抽屜里,不論怎樣放,至少有一個(gè)抽屜放有兩個(gè)或兩個(gè)以上的蘋果,這就是抽屜原理最簡(jiǎn)單的例子.抽屜原則有時(shí)也被稱為鴿巢原理,它是德國數(shù)學(xué)家狄利克雷首先明確的提出來并用以證明一些數(shù)論中的問題,因此,也稱為狄利克雷原則。它是組合數(shù)學(xué)中一個(gè)重要的原理。把它推廣到一般情形有以下幾種表現(xiàn)形式。1. 若有個(gè)元素放進(jìn)個(gè)集合,則必存在一個(gè)集合至少放2個(gè)元素;2. 若把個(gè)元素放進(jìn)個(gè)集合,則必存在一個(gè)集合至少放有個(gè)元素;3.把個(gè)物體,按照任意方式全部放入個(gè)抽屜中,有兩種情況:當(dāng)能整除時(shí),一定存在一個(gè)抽屜中至少放入了個(gè)物體;當(dāng)不能整除時(shí),一定存在一個(gè)抽屜中至少放
2、入了個(gè)物體.二、容斥原理當(dāng)我們對(duì)某些對(duì)象的數(shù)目從整體上計(jì)數(shù)碰到困難時(shí),可以考慮將整體分解為幾個(gè)部分,通過對(duì)每個(gè)部分的計(jì)數(shù)來實(shí)現(xiàn)對(duì)整體的計(jì)數(shù). 這一方法就是容斥原理.將整體分解為部分,也就是將集合表示成它的一組兩兩互異的非空真子集的并集,即,其中,,則集合叫做集合的一個(gè)覆蓋. 當(dāng)集合中的任意兩個(gè)集合都不相交時(shí),稱為集合的一個(gè)(完全)劃分.即是集合的一個(gè)覆蓋,且.如為集合的劃分,則(為了方便,我們用來表示集合的元素個(gè)數(shù),即),但是,要找到一個(gè)劃分并且其中所有子集易于計(jì)數(shù)的有時(shí)并非易事. 我們可以考慮通過對(duì)任意的集族中的子集的計(jì)數(shù)來計(jì)算,當(dāng)集族只是的覆蓋,而不是劃分時(shí),顯然有. 因?yàn)樵谟?jì)算時(shí)出現(xiàn)了對(duì)
3、某些元素的重復(fù)計(jì)數(shù),為了計(jì)算,就得將式右邊重復(fù)計(jì)算的部分減去,如果減得多了,還得再加上,也就是說我們要做“多退少補(bǔ)”的工作.完成上述工作的準(zhǔn)則就是容斥原理,是十九世紀(jì)英國數(shù)學(xué)家西爾維斯提出的,容斥原理有兩個(gè)公式.1. 容斥公式定理1設(shè)為有限集,則.容斥公式常用來計(jì)算至少具有某幾個(gè)性質(zhì)之一的元素的數(shù)目.2. 篩法公式與容斥公式討論的計(jì)數(shù)問題相反,有時(shí)需要計(jì)算不具有某幾個(gè)性質(zhì)中的任何一個(gè)性質(zhì)的元素的個(gè)數(shù),即.定理2設(shè)為有限集的子集,則.II. 典型例題精講例題:任意400人中至少有兩個(gè)人的生日相同.分析:生日從1月1日排到12月31日,共有366個(gè)不相同的生日,我們把366個(gè)不同的生日看作366個(gè)
4、抽屜,400人視為400個(gè)蘋果,由表現(xiàn)形式1可知,至少有兩人在同一個(gè)抽屜里,所以這400人中有兩人的生日相同.解:將一年中的366天視為366個(gè)抽屜,400個(gè)人看作400個(gè)蘋果,由抽屜原理可以得知至少有兩人的生日相同.例題:邊長為1的正方形中,任意放入9個(gè)點(diǎn),求證這9個(gè)點(diǎn)中任取3個(gè)點(diǎn)組成的三角形中,至少有一個(gè)的面積不超過.解:將邊長為1的正方形等分成邊長為的四個(gè)小正方形,視這四個(gè)正方形為抽屜,9個(gè)點(diǎn)任意放入這四個(gè)正方形中,根據(jù)抽屜原理,必有三點(diǎn)落入同一個(gè)正方形內(nèi).現(xiàn)取出這個(gè)正方形來加以討論.把落在這個(gè)正方形中的三點(diǎn)記為通過這三點(diǎn)中的任意一點(diǎn)(如)作平行線,如圖可知:CEGFDMISSING I
5、MAGEMISSING IMAGEMISSING IMAGEMISSING IMAGEMISSING IMAGE例題:任取5個(gè)整數(shù),必然能夠從中選出三個(gè),使它們的和能夠被3整除.證明:任意給一個(gè)整數(shù),它被3除,余數(shù)可能為0,1,2,我們把被3除余數(shù)為0,1,2的整數(shù)各歸入類.至少有一類包含所給個(gè)數(shù)中的至少兩個(gè).因此可能出現(xiàn)兩種情況: . 某一類至少包含三個(gè)數(shù);. 某兩類各含兩個(gè)數(shù),第三類包含一個(gè)數(shù).若是第一種情況,就在至少包含三個(gè)數(shù)的那一類中任取三數(shù),其和一定能被3整除;若是第二種情況,在三類中各取一個(gè)數(shù),其和也能被3整除.綜上所述,原命題正確.例題:九條直線中的每一條直線都將正方形分成面積比
6、為23的梯形,證明:這九條直線中至少有三條經(jīng)過同一點(diǎn).證明:如圖,設(shè)是一條這樣的直線,作這兩個(gè)梯形的中位線因?yàn)檫@兩個(gè)梯形的高相等,所以它們的面積之比等于中位線長的比,即,從而點(diǎn)有確定的位置(它在正方形一對(duì)對(duì)邊中點(diǎn)的連線上,并且).由幾何上的對(duì)稱性,這種點(diǎn)共有四個(gè),即圖中的已知的九條適合條件的分割直線中的每一條必須經(jīng)過這四點(diǎn)中的一點(diǎn).把看成四個(gè)抽屜,九條直線當(dāng)成個(gè)蘋果,即可得出必定有條分割線經(jīng)過同一點(diǎn).例題:某校派出學(xué)生204人上山植樹15301株,其中最少一人植樹50株,最多一人植樹100株,則至少有5人植樹的株數(shù)相同.證明:按植樹的多少,從50到100株可以構(gòu)造51個(gè)抽屜,則個(gè)問題就轉(zhuǎn)化為至
7、少有5人植樹的株數(shù)在同一個(gè)抽屜里.(用反證法)假設(shè)無人或人以上植樹的株數(shù)在同一個(gè)抽屜里,那只有人以下植樹的株數(shù)在同一個(gè)抽屜里,而參加植樹的人數(shù)為204人,所以,每個(gè)抽屜最多有4人,故植樹的總株數(shù)最多有:4(5051100)1530015301得出矛盾.因此,至少有人植樹的株數(shù)相同.例題6(2016北京文科高考試題)某網(wǎng)店統(tǒng)計(jì)了連續(xù)三天售出商品的種類情況:第一天售出19種商品,第二天售出13種商品,第三天售出18種商品;前兩天都售出的商品有3種,后兩天都售出的商品有4種,則該網(wǎng)店三天售出的商品至少有種.解析:設(shè)三天銷售商品種類的集合分別是,由題已知.由容斥原理可得要求的最小值,只需求即的最大值.
8、而,當(dāng)這個(gè)元素均在中時(shí),最大值為.所以的最小值為.例題7設(shè)集合,是的子集,并且的元素或是的倍數(shù),或是的倍數(shù),或是的倍數(shù),試問的元素最多有幾個(gè)?解析:設(shè),則注意到,由容斥原理,可得所以的元素最多有個(gè)例題8給定正整數(shù),某個(gè)協(xié)會(huì)中恰好有個(gè)人,他們屬于6個(gè)委員會(huì),每個(gè)委員會(huì)至少由個(gè)人組成,證明:必有兩個(gè)委員會(huì),他們的公共成員數(shù)不小于.證明:設(shè)表示6個(gè)委員會(huì)的成員集合,則, 所以.如果任意,均有,那么,矛盾. 所以必存在使得.練習(xí)題:1邊長為1的等邊三角形內(nèi)有5個(gè)點(diǎn),證明:這5個(gè)點(diǎn)中一定有距離小于0.5的兩點(diǎn).2邊長為1的等邊三角形內(nèi),若有個(gè)點(diǎn),則至少存在2點(diǎn)距離小于.3求證:任意四個(gè)整數(shù)中,至少有兩個(gè)
9、整數(shù)的差能夠被3整除.4某校高一某班有50名新生,試說明其中一定有兩個(gè)人的熟人一樣多.5某個(gè)年級(jí)有202人參加考試,滿分為100分,且得分都為整數(shù),總得分為10101分,則至少有3人得分相同.6. 求1,2,3,100中不能被2,3,5整除的數(shù)的個(gè)數(shù)。解答:記,由容斥原理,所以不能被2,3,5整除的數(shù)有個(gè)。7.S是集合1,2,2004的子集,S中的任意兩個(gè)數(shù)的差不等于4或7,問S中最多含有多少個(gè)元素?解答:將任意連續(xù)的11個(gè)整數(shù)排成一圈如右圖所示。由題目條件可知每相鄰兩個(gè)數(shù)至多有一個(gè)屬于S,將這11個(gè)數(shù)按連續(xù)兩個(gè)為一組,分成6組,其中一組只有一個(gè)數(shù),若S含有這11個(gè)數(shù)中至少6個(gè),則必有兩個(gè)數(shù)在
10、同一組,與已知矛盾,所以S至多含有其中5個(gè)數(shù)。又因?yàn)?004=18211+2,所以S一共至多含有1825+2=912個(gè)元素,另一方面,當(dāng)時(shí),恰有,且S滿足題目條件,所以最少含有912個(gè)元素。8. 求所有自然數(shù),使得存在實(shí)數(shù)滿足:解答:當(dāng)時(shí),;當(dāng)時(shí),;當(dāng)時(shí),。接下來證當(dāng)時(shí),不存在滿足條件。令,則所以必存在某兩個(gè)下標(biāo),使得,所以或,即,所以或,。()若,考慮,有或,即,設(shè),則,導(dǎo)致矛盾,故只有考慮,有或,即,設(shè),則,推出矛盾,設(shè),則,又推出矛盾, 所以故當(dāng)時(shí),不存在滿足條件的實(shí)數(shù)。()若,考慮,有或,即,這時(shí),推出矛盾,故??紤],有或,即=3,于是,矛盾。因此,所以,這又矛盾,所以只有,所以。故當(dāng)
11、時(shí),不存在滿足條件的實(shí)數(shù)。9. 設(shè)A=1,2,3,4,5,6,B=7,8,9,n,在A中取三個(gè)數(shù),B中取兩個(gè)數(shù)組成五個(gè)元素的集合,求的最小值。解答:設(shè)B中每個(gè)數(shù)在所有中最多重復(fù)出現(xiàn)次,則必有。若不然,數(shù)出現(xiàn)次(),則在出現(xiàn)的所有中,至少有一個(gè)A中的數(shù)出現(xiàn)3次,不妨設(shè)它是1,就有集合1,其中,為滿足題意的集合。必各不相同,但只能是2,3,4,5,6這5個(gè)數(shù),這不可能,所以20個(gè)中,B中的數(shù)有40個(gè),因此至少是10個(gè)不同的,所以。當(dāng)時(shí),如下20個(gè)集合滿足要求:1,2,3,7,8, 1,2,4,12,14, 1,2,5,15,16, 1,2,6,9,10,1,3,4,10,11, 1,3,5,13,14, 1,3,6,12,15, 1,4,5,7,9,1,4,6,13,16, 1,5,6,8,11, 2,3,4,13,15, 2,3,5,9,11,2,3,6,14,16, 2,4,5,8,10, 2,4,6,7,11, 2,5,6,12,13,3,4,5,
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 滾珠絲杠課程設(shè)計(jì)圖紙
- 自行車的人機(jī)課程設(shè)計(jì)
- 荒島植物辨識(shí)課程設(shè)計(jì)
- 泵房的課程設(shè)計(jì)
- 智慧物流課課程設(shè)計(jì)
- 英語思維導(dǎo)圖課程設(shè)計(jì)
- 古泉1100kV千伏GIS安裝施工方案(報(bào)公司審核)
- 植物根莖科學(xué)課程設(shè)計(jì)
- 長沙交通集團(tuán)日常維修定點(diǎn)項(xiàng)目招標(biāo)文件
- 物體打擊 課程設(shè)計(jì)
- 水利水電工程安全管理制度例文(三篇)
- 2025四川宜賓市南溪區(qū)屬國企業(yè)招聘融資人員6人管理單位筆試遴選500模擬題附帶答案詳解
- 人教版2024-2025學(xué)年第一學(xué)期八年級(jí)物理期末綜合復(fù)習(xí)練習(xí)卷(含答案)
- 《上帝擲骰子嗎:量子物理史話》導(dǎo)讀學(xué)習(xí)通超星期末考試答案章節(jié)答案2024年
- 病例報(bào)告表(CRF)模板
- 國家開放大學(xué)畢業(yè)生登記表
- CCC例行檢驗(yàn)和確認(rèn)檢驗(yàn)程序
- 初中物理競(jìng)賽教程(基礎(chǔ)篇)第16講比熱容
- 親子鑒定書(共3頁)
- 容器支腿計(jì)算公式(支腿計(jì)算主要用于立式容器的支腿受力及地腳螺栓計(jì)算)
- 建設(shè)工程項(xiàng)目施工安全管理流程圖3頁
評(píng)論
0/150
提交評(píng)論