高中數(shù)學(xué)競(jìng)賽專題講座2 集合與容斥原理

1、容斥原理與抽屜原理一、基礎(chǔ)知識(shí) （一）有限集合所含元素個(gè)數(shù)的幾個(gè)簡(jiǎn)單性質(zhì)（容斥原理） 設(shè)表示集合所含元素的個(gè)數(shù),（1）, 當(dāng)時(shí)， 推廣到個(gè)集合的情況，（2）變形：逐步淘汰原理（篩法公式）設(shè)s是有限集，()，在s中的補(bǔ)集為()，則+（三）集合的劃分：若，且，則這些子集的全集叫i的一個(gè)-劃分。相對(duì)補(bǔ)集：稱屬于a而不屬于b的全體元素，組成的集合為b對(duì)a的相對(duì)補(bǔ)集或差集，記作a-b。 （四）計(jì)數(shù)原理定理1 分類計(jì)數(shù)原理（加法原理）：做一件事有類辦法，第一類辦法中有種不同的方法，第二類辦法中有種不同的方法，第類辦法中有種不同的方法，那么完成這件事一共有種不同的方法。定理2 分步計(jì)數(shù)原理（乘法原理）：做一

2、件事分個(gè)步驟，第一步有種不同的方法，第二步有種不同的方法，第步有種不同的方法，那么完成這件事一共有種不同的方法。應(yīng)用舉例例1、某班對(duì)數(shù)學(xué)、物理、化學(xué)三科總評(píng)成績統(tǒng)計(jì)如下：優(yōu)秀的人數(shù)：數(shù)學(xué)21個(gè)，物理19個(gè)，化學(xué)20個(gè)，數(shù)學(xué)物理都優(yōu)秀9人，物理化學(xué)都優(yōu)秀7人?；瘜W(xué)數(shù)學(xué)都優(yōu)秀8人。這個(gè)班有5人任何一科都不優(yōu)秀。那么確定這個(gè)班人數(shù)以及僅有一科優(yōu)秀的三科分別有多少個(gè)人。分析：自然地設(shè)a=數(shù)學(xué)總評(píng)優(yōu)秀的人 b=物理總評(píng)優(yōu)秀的人 c=化學(xué)總評(píng)優(yōu)秀的人則已知|a|=21 |b|=19 |c|=20這表明全班人數(shù)在41至48人之間。僅數(shù)學(xué)優(yōu)秀的人數(shù)是可見僅數(shù)學(xué)優(yōu)秀的人數(shù)在4至11人之間。同理僅物理優(yōu)秀的人數(shù)在

3、3至10人之間。同理僅化學(xué)優(yōu)秀的人數(shù)在5至12人之間。例2、集合a，b是i=1，2，3，4，5，6，7，8，9，0的子集，若，求有序集合對(duì)（a，b）的個(gè)數(shù)；分析：集合i可劃分為三個(gè)不相交的子集；ab，ba，中的每個(gè)元素恰屬于其中一個(gè)子集，10個(gè)元素共有310種可能，每一種可能確定一個(gè)滿足條件的集合對(duì)，所以集合對(duì)有310個(gè)。例3、 求1，2，3，100中不能被2，3，5整除的數(shù)的個(gè)數(shù)。分析：記，由容斥原理，所以不能被2，3，5整除的數(shù)有個(gè)。例4、設(shè)a1,2，3，n，對(duì)xa，設(shè)x中各元素之和為nx，求nx的總和.分析已知的所有的子集共有個(gè).而對(duì)于,顯然中包含的子集與集合的子集個(gè)數(shù)相等.這就說明在集

4、合的所有子集中一共出現(xiàn)次,即對(duì)所有的求和,可得【解】集合的所有子集的元素之和為=說明本題的關(guān)鍵在于得出中包含的子集與集合的子集個(gè)數(shù)相等.這種一一對(duì)應(yīng)的方法在集合問題以及以后的組合總是中應(yīng)用非常廣泛.例5、給定集合的個(gè)子集：，滿足任何兩個(gè)子集的交集非空，并且再添加i的任何一個(gè)其他子集后將不再具有該性質(zhì)，求的值。分析：將i的子集作如下配對(duì)：每個(gè)子集和它的補(bǔ)集為一對(duì)，共得對(duì)，每一對(duì)不能同在這個(gè)子集中，因此，；其次，每一對(duì)中必有一個(gè)在這個(gè)子集中出現(xiàn)，否則，若有一對(duì)子集未出現(xiàn)，設(shè)為c1a與a，并設(shè)，則，從而可以在個(gè)子集中再添加，與已知矛盾，所以。綜上，。例6、1992位科學(xué)家，每人至少與1329人合作過

5、，那么，其中一定有四位數(shù)學(xué)家兩兩合作過。分析：在與一個(gè)人a合作的人中我們找到b。再說明一定有人與a和b都合作過為c。最后再說明有人與a、b、c都合作過為d，那么a、b、c、d就是找的人了。 證明：一個(gè)人a。不妨設(shè)b與之合作。那么。即c與a和b均合作過，分別表示與a、b合作過的人的集合。同樣地，。所以存在。則a、b、c、d就是所求，證畢。說明：把一個(gè)普通的敘述性問題轉(zhuǎn)化為集合的語言描述的問題通常為解題的關(guān)鍵之處，也是同學(xué)們需加強(qiáng)的。（五）抽屜原理 在數(shù)學(xué)問題中有一類與“存在性”有關(guān)的問題，例如：“13個(gè)人中至少有兩個(gè)人出生在相同月份”；“某校400名學(xué)生中，一定存在兩名學(xué)生，他們?cè)谕惶爝^生日”

6、；“2003個(gè)人任意分成200個(gè)小組，一定存在一組，其成員數(shù)不少于11”。這類存在性問題中，“存在”的含義是“至少有一個(gè)”。在解決這類問題時(shí)，只要求指明存在，一般并不需要指出哪一個(gè)，也不需要確定通過什么方式把這個(gè)存在的東西找出來。這類問題相對(duì)來說涉及到的運(yùn)算較少，依據(jù)的理論也不復(fù)雜，這些理論稱為“抽屜原理”。 抽屜原則有時(shí)也被稱為鴿巢原理，它是德國數(shù)學(xué)家狄利克雷首先明確的提出來并用以證明一些數(shù)論中的問題，因此，也稱為狄利克雷原則。它是組合數(shù)學(xué)中一個(gè)重要的原理。把它推廣到一般情形有以下幾種表現(xiàn)形式。（一）抽屜原理的基本形式 定理1、如果把n+1個(gè)元素分成n個(gè)集合，那么不管怎么分，都存在一個(gè)集合，

7、其中至少有兩個(gè)元素。 證明：（用反證法）若不存在至少有兩個(gè)元素的集合，則每個(gè)集合至多1個(gè)元素，從而n個(gè)集合至多有n個(gè)元素，此與共有n+1個(gè)元素矛盾，故命題成立。 例1、 已知在邊長為1的等邊三角形內(nèi)（包括邊界）有任意五個(gè)點(diǎn)（圖1）。證明：至少有兩個(gè)點(diǎn)之間的距離不大于. 如果把條件（包括邊界）去掉，則結(jié)論可以修改為：至少有兩個(gè)點(diǎn)之間的距離小于 .分析：5個(gè)點(diǎn)的分布是任意的。如果要證明“在邊長為1的等邊三角形內(nèi)（包括邊界）有5個(gè)點(diǎn)，那么這5個(gè)點(diǎn)中一定有距離不大于的兩點(diǎn)”，則順次連接三角形三邊中點(diǎn)，即三角形的三條中位線，可以分原等邊三角形為4個(gè)全等的邊長為的小等邊三角形，則5個(gè)點(diǎn)中必有2點(diǎn)位于同一個(gè)

8、小等邊三角形中（包括邊界），其距離便不大于。 以上結(jié)論要由定理“三角形內(nèi)（包括邊界）任意兩點(diǎn)間的距離不大于其最大邊長”來保證，下面我們就來證明這個(gè)定理。如圖2，設(shè)bc是abc的最大邊，p，m是abc內(nèi)（包括邊界）任意兩點(diǎn)，連接pm，過p分別作ab、bc邊的平行線，過m作ac邊的平行線，設(shè)各平行線交點(diǎn)為p、q、n，那么pqn=c，qnp=a因?yàn)閎cab，所以ac，則qnppqn，而qmpqnppqn（三角形的外角大于不相鄰的內(nèi)角），所以 pqpm。顯然bcpq，故bcpm。由此我們可以推知，邊長為的等邊三角形內(nèi)（包括邊界）兩點(diǎn)間的距離不大于。 說明：（1）這里是用等分三角形的方法來構(gòu)造“抽屜”。

9、類似地，還可以利用等分線段、等分正方形的方法來構(gòu)造“抽屜”。例如“任取n+1個(gè)正數(shù)ai，滿足0ai1（i=1,2,n+1），試證明：這n+1個(gè)數(shù)中必存在兩個(gè)數(shù)，其差的絕對(duì)值小于”。又如：“在邊長為1的正方形內(nèi)任意放置五個(gè)點(diǎn)，求證：其中必有兩點(diǎn)，這兩點(diǎn)之間的距離不大于。 例2、 從1-100的自然數(shù)中，任意取出51個(gè)數(shù)，證明其中一定有兩個(gè)數(shù)，它們中的一個(gè)是另一個(gè)的整數(shù)倍。 分析：本題似乎茫無頭緒，從何入手？其關(guān)鍵何在？其實(shí)就在“兩個(gè)數(shù)”，其中一個(gè)是另一個(gè)的整數(shù)倍。我們要構(gòu)造“抽屜”，使得每個(gè)抽屜里任取兩個(gè)數(shù)，都有一個(gè)是另一個(gè)的整數(shù)倍，這只有把公比是正整數(shù)的整個(gè)等比數(shù)列都放進(jìn)去同一個(gè)抽屜才行，這里

10、用得到一個(gè)自然數(shù)分類的基本知識(shí)：任何一個(gè)正整數(shù)都可以表示成一個(gè)奇數(shù)與2的方冪的積，即若mn+,kn+，nn,則m=(2k-1)2n，并且這種表示方式是唯一的，如1=12，2=121，3=32， 證明：因?yàn)槿魏我粋€(gè)正整數(shù)都能表示成一個(gè)奇數(shù)乘2的方冪，并且這種表示方法是唯一的，所以我們可把1-100的正整數(shù)分成如下50個(gè)抽屜（因?yàn)?-100中共有50個(gè)奇數(shù)）： （1）1，12，122，123，124，125，126；2）3，32，322，323，324，325；3）5，52，522，523，524； （4）7，72，722，723；（5）9，92，922，923；（6）11，112，1122，11

11、23；（25）49，492；（26）51；（50）99。 這樣，1-100的正整數(shù)就無重復(fù)，無遺漏地放進(jìn)這50個(gè)抽屜內(nèi)了。從這100個(gè)數(shù)中任取51個(gè)數(shù)，也即從這50個(gè)抽屜內(nèi)任取51個(gè)數(shù)，根據(jù)抽屜原則，其中必定至少有兩個(gè)數(shù)屬于同一個(gè)抽屜，即屬于（1）-（25）號(hào)中的某一個(gè)抽屜，顯然，在這25個(gè)抽屜中的任何同一個(gè)抽屜內(nèi)的兩個(gè)數(shù)中，一個(gè)是另一個(gè)的整數(shù)倍。 說明： （1）從上面的證明中可以看出，本題能夠推廣到一般情形：從1-2n的自然數(shù)中，任意取出n+1個(gè)數(shù)，則其中必有兩個(gè)數(shù)，它們中的一個(gè)是另一個(gè)的整數(shù)倍。想一想，為什么？因?yàn)?-2n中共含1，3，2n-1這n個(gè)奇數(shù)，因此可以制造n個(gè)抽屜，而n+1n，

12、由抽屜原則，結(jié)論就是必然的了。給n以具體值，就可以構(gòu)造出不同的題目。例2中的n取值是50，還可以編制相反的題目，如：“從前30個(gè)自然數(shù)中最少要（不看這些數(shù)而以任意方式地）取出幾個(gè)數(shù)，才能保證取出的數(shù)中能找到兩個(gè)數(shù)，其中較大的數(shù)是較小的數(shù)的倍數(shù)？” (2）如下兩個(gè)問題的結(jié)論都是否定的（n均為正整數(shù)）想一想，為什么？ 從2，3，4，2n+1中任取n+1個(gè)數(shù)，是否必有兩個(gè)數(shù)，它們中的一個(gè)是另一個(gè)的整數(shù)倍？從1，2，3，2n+1中任取n+1個(gè)數(shù)，是否必有兩個(gè)數(shù)，它們中的一個(gè)是另一個(gè)的整數(shù)倍？（3）如果將（2）中兩個(gè)問題中任取的n+1個(gè)數(shù)增加1個(gè)，都改成任取n+2個(gè)數(shù)，則它們的結(jié)論是肯定的還是否定的？你

13、能判斷證明嗎？ 例3從1到25的25個(gè)自然數(shù)中任意取出7個(gè)數(shù)，證明：取出的數(shù)中一定有兩個(gè)數(shù)，這兩個(gè)數(shù)中大數(shù)不超過小數(shù)的1.5倍。 證明：把前25個(gè)自然數(shù)分成下面6組： 1； 2，3； 4，5，6； 7，8，9，10； 11，12，13，14，15，16； 17，18，19，20，21，22，23， 因?yàn)閺那?5個(gè)自然數(shù)中任意取出7個(gè)數(shù)，所以至少有兩個(gè)數(shù)取自上面第組到第組中的某同一組，這兩個(gè)數(shù)中大數(shù)就不超過小數(shù)的1.5倍。說明：（1）本題可以改變敘述如下：在前25個(gè)自然數(shù)中任意取出7個(gè)數(shù)，求證其中存在兩個(gè)數(shù)，它們相互的比值在內(nèi)。顯然，必須找出一種能把前25個(gè)自然數(shù)分成6（7-1=6）個(gè)集合的方法

14、，不過分類時(shí)有一個(gè)限制條件：同一集合中任兩個(gè)數(shù)的比值在內(nèi)，故同一集合中元素的數(shù)值差不得過大。這樣，我們可以用如上一種特殊的分類法：遞推分類法： 從1開始，顯然1只能單獨(dú)作為1個(gè)集合1；否則不滿足限制條件.能與2同屬于一個(gè)集合的數(shù)只有3，于是2，3為一集合。如此依次遞推下去，使若干個(gè)連續(xù)的自然數(shù)屬于同一集合，其中最大的數(shù)不超過最小的數(shù)的倍，就可以得到滿足條件的六個(gè)集合。 （2）如果我們按照（1）中的遞推方法依次造“抽屜”，則第7個(gè)抽屜為 26，27，28，29，30，31，32，33，34，35，36，37，38，39；第8個(gè)抽屜為：40，41，42，60；第9個(gè)抽屜為：61，62，63，90，

15、91； 例4在坐標(biāo)平面上任取五個(gè)整點(diǎn)（該點(diǎn)的橫縱坐標(biāo)都取整數(shù)），證明：其中一定存在兩個(gè)整點(diǎn)，它們的連線中點(diǎn)仍是整點(diǎn)。 分析與解答：由中點(diǎn)坐標(biāo)公式知，坐標(biāo)平面兩點(diǎn)（x1,y1）、（x2,y2）的中點(diǎn)坐標(biāo)是。欲使都是整數(shù)，必須而且只須x1與x2，y1與y2的奇偶性相同。坐標(biāo)平面上的任意整點(diǎn)按照橫縱兩個(gè)坐標(biāo)的奇偶性考慮有且只有如下四種：（奇數(shù)、奇數(shù)），（偶數(shù)，偶數(shù)），（奇數(shù)，偶數(shù)），（偶數(shù)，奇數(shù)）以此構(gòu)造四個(gè)“抽屜”，則在坐標(biāo)平面上任取五個(gè)整點(diǎn)，那么至少有兩個(gè)整點(diǎn)，屬于同一個(gè)“抽屜”因此它們連線的中點(diǎn)就必是整點(diǎn)。 說明：我們可以把整點(diǎn)的概念推廣：如果（x1,x2,xn）是n維（元）有序數(shù)組，且x1,

16、x2,xn中的每一個(gè)數(shù)都是整數(shù)，則稱（x1,x2,xn）是一個(gè)n維整點(diǎn)（整點(diǎn)又稱格點(diǎn)）。如果對(duì)所有的n維整點(diǎn)按每一個(gè)xi的奇偶性來分類，由于每一個(gè)位置上有奇、偶兩種可能性，因此共可分為222=2n個(gè)類。這是對(duì)n維整點(diǎn)的一種分類方法。當(dāng)n=3時(shí)，23=8，此時(shí)可以構(gòu)造命題：“任意給定空間中九個(gè)整點(diǎn)，求證它們之中必有兩點(diǎn)存在，使連接這兩點(diǎn)的直線段的內(nèi)部含有整點(diǎn)”。 例5在任意給出的100個(gè)整數(shù)中，都可以找出若干個(gè)數(shù)來（可以是一個(gè)數(shù)），它們的和可被100整除。 分析：本題也似乎是茫無頭緒，無從下手，其關(guān)鍵何在？仔細(xì)審題，它們的“和”能“被100整除”應(yīng)是做文章的地方。如果把這100個(gè)數(shù)排成一個(gè)數(shù)列，

17、用sm記其前m項(xiàng)的和，則其可構(gòu)造s1，s2，s100共100個(gè)和數(shù)。討論這些“和數(shù)”被100除所得的余數(shù)。注意到s1，s2，s100共有100個(gè)數(shù)，一個(gè)數(shù)被100除所得的余數(shù)有0，1，2，99共100種可能性?！疤O果”數(shù)與“抽屜”數(shù)一樣多，如何排除“故障”？證明：設(shè)已知的整數(shù)為a1,a2,a100考察數(shù)列a1,a2,a100的前n項(xiàng)和構(gòu)成的數(shù)列s1，s2，s100。 如果s1，s2，s100中有某個(gè)數(shù)可被100整除，則命題得證。否則s1，s2，s100。 均不能被100整除，這樣，它們被100除后余數(shù)必是1，2，99中的元素。由抽屜原理i知，s1，s2，s100中必有兩個(gè)數(shù)，它們被100除后具

18、有相同的余數(shù)。不妨設(shè)這兩個(gè)數(shù)為si，sj（ij），則100（sj-si），即100。命題得證。 說明：有時(shí)候直接對(duì)所給對(duì)象作某種劃分，是很難構(gòu)造出恰當(dāng)?shù)某閷系?。這時(shí)候，我們需要對(duì)所給對(duì)象先作一些變換，然后對(duì)變換得到的對(duì)象進(jìn)行分類，就可以構(gòu)造出恰當(dāng)?shù)某閷?。本題直接對(duì)an進(jìn)行分類是很難奏效的。但由an構(gòu)造出sn后，再對(duì)sn進(jìn)行分類就容易得多. 另外，對(duì)sn按模100的剩余類劃分時(shí)，只能分成100個(gè)集合，而sn只有100項(xiàng)，似乎不能應(yīng)用抽屜原則。但注意到余數(shù)為0的類恰使結(jié)論成立，于是通過分別情況討論后，就可去掉余數(shù)為0的類，從而轉(zhuǎn)化為100個(gè)數(shù)分配在剩下的99個(gè)類中。 例6、一個(gè)集合含有10個(gè)互不相

19、同的兩位數(shù)。試證，這個(gè)集合必有2個(gè)無公共元素的子集合，此兩子集的各數(shù)之和相等。分析：兩位數(shù)共有10,11，,99，計(jì)99990個(gè)，最大的10個(gè)兩位數(shù)依次是90,91，,99，其和為945，因此，由10個(gè)兩位數(shù)組成的任意一個(gè)集合中，其任一個(gè)子集中各元素之和都不會(huì)超過945，而它的非空子集卻有21011023個(gè)，這是解決問題的突破口。解：已知集合含有10個(gè)不同的兩位數(shù)，因它含有10個(gè)元素，故必有2101024個(gè)子集，其中非空子集有1023個(gè)，每一個(gè)子集內(nèi)各數(shù)之和都不超過90919899945133，就有15n1995.故取出所有大于133而不超過1995的整數(shù). 由于這時(shí)己取出了159=135,

20、15133=1995. 故9至133的整數(shù)都不能再取，還可取1至8這8個(gè)數(shù)，即共取出1995133+8=1870個(gè)數(shù), 這說明所求數(shù)1870.另一方面，把k與15k配對(duì)，（k不是15的倍數(shù)，且1k133）共得1338=125對(duì)，每對(duì)數(shù)中至多能取1個(gè)數(shù)為a的元素，這說明所求數(shù)1870，綜上可知應(yīng)填1870.9、集合的容量是指集合中元素的和則滿足條件“，且若時(shí)，必有”的所有非空集合的容量的總和是 （用具體數(shù)字作答）先找出滿足條件的單元素和二元素的集合有：，將這四個(gè)集合中的元素任意組合起來也滿足要求，則所有符合條件的集合a中元素的總和是 ：10、設(shè)n是正整數(shù)，集合m=1，2，2n求最小的正整數(shù)k，使

21、得對(duì)于m的任何一個(gè)k元子集，其中必有4個(gè)互不相同的元素之和等于4 n +1,則k= 解：考慮m的n+2元子集p=nl，n，n+1，2np中任何4個(gè)不同元素之和不小于(n1)+n+( n +1)+( n +2)=4 n +2，所以kn +3將m的元配為n對(duì)，bi=(i，2 n +1i)，1in 對(duì)m的任一n+3元子集a，必有三對(duì)同屬于a(i1、i 2、i 3兩兩不同)又將m的元配為n1對(duì)，c i (i，2ni)，1in1對(duì)m的任一n+3元子集a，必有一對(duì)同屬于a，這一對(duì)必與中至少一個(gè)無公共元素，這4個(gè)元素互不相同，且和為2 n +1+2 n =4 n +1,最小的正整數(shù)k= n +31011、（

22、2013福建高一）對(duì)給定的正整數(shù)（），由不大于的連續(xù)5個(gè)正整數(shù)的和組成集合，由不大于的連續(xù)6個(gè)正整數(shù)的和組成集合，若集合的元素個(gè)數(shù)為2013，則的最大值為 12088 ?！窘獯稹坑蓷l件知集合由形如的數(shù)構(gòu)成，其中為正整數(shù)，且。集合由形如的數(shù)構(gòu)成，其中為正整數(shù)，且。由知，所以。設(shè)（為正整數(shù)），則，。由，知，。 由形如的數(shù)構(gòu)成，其中為正整數(shù)，且。 集合的元素個(gè)數(shù)為。由的元素個(gè)數(shù)為2013知，。 ，。的最大值為。12、集合1，2，3n可以劃分成個(gè)互不相交的三元集合，其中，則滿足條件的最小正整數(shù)= 【解】 設(shè)其中第個(gè)三元集為則1+2+所以。當(dāng)為偶數(shù)時(shí)，有，所以，當(dāng)為奇數(shù)時(shí)，有，所以，當(dāng)時(shí)，集合1，11，

23、4，2，13，5，3，15，6，9，12，7，10，14，8滿足條件，所以的最小值為5。解答題 1、設(shè)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ù)在同一組，與已知矛盾，所以s至多含有其中5個(gè)數(shù)。又因?yàn)?004=18211+2，所以s一共至多含有1825+2=912個(gè)元素，另一方面，當(dāng)時(shí)，恰有，且s滿足題目條件，所以最少含有912個(gè)元素。2、（2011甘肅）

24、設(shè)是一正整數(shù)， 由不大于的連續(xù)10個(gè)正整數(shù)的和組成集合，由不大于的連續(xù)11個(gè)正整數(shù)的和組成集合。若的元素個(gè)數(shù)是181，求的最大值和最小值。解：顯然，為求的元素個(gè)數(shù)，令 ，則。- 再令，則得因?yàn)?，可取值，此時(shí)的相應(yīng)取值為。 注意到 符合的取值范圍，舍去不合乎要求的值，則知集合的元素個(gè)數(shù)為。令 ， 則 即，于是的最大值和最小值分別為2011和2001 3、任取 5 個(gè)整數(shù)，必然能夠從中選出三個(gè)，使它們的和能夠被 3 整除 證明：任意給一個(gè)整數(shù)，它被 3 除，余數(shù)可能為 0，1，2，我們把被 3 除余數(shù)為 0，1，2 的整數(shù)各歸 入類 r，r1，r2至少有一類包含所給個(gè)數(shù)中的至少兩個(gè)因此可能出現(xiàn)兩種

25、情況： 1某一類至少包含三個(gè)數(shù)； 2某兩類各含兩個(gè)數(shù)，第三類包含一個(gè)數(shù) 若是第一種情況，就在至少包含三個(gè)數(shù)的那一類中任取三數(shù)，其和一定能被 3 整除； 若是第二種情況，在三類中各取一個(gè)數(shù)，其和也能被 3 整除 綜上所述，原命題正確4、把1到10的自然數(shù)擺成一個(gè)圓圈，證明一定存在在個(gè)相鄰的數(shù)，它們的和數(shù)大于17.證明 如圖12-1，設(shè)a1，a2，a3，a9，a10分別代表不超過10的十個(gè)自然數(shù)，它們圍成一個(gè)圈，三個(gè)相鄰的數(shù)的組成是（a1，a2，a3），（a2，a3，a4），（a3，a4，a5），,（a9，a10，a1）,（a10，a1，a2）共十組.現(xiàn)把它們看作十個(gè)抽屜，每個(gè)抽屜的物體數(shù)是a1+

26、a2+a3，a2+a3+a4，a3+a4+a5，a9+a10+a1，a10+a1+a2,由于（a1+a2+a3）+（a2+a3+a4）+（a9+a10+a1）+（a10+a1+a2）=3(a1+a2+a9+a10)=3(1+2+9+10)=根據(jù)原則2,至少有一個(gè)括號(hào)內(nèi)的三數(shù)和不少于17,即至少有三個(gè)相鄰的數(shù)的和不小于17.5、任意給定7個(gè)實(shí)數(shù)，則必存在兩個(gè)數(shù)，使得 6、設(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次

27、，不妨設(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，

28、5，12，16， 3，4，6，8，9， 3，5，6，7，10， 4，5，6，14，15。7、把個(gè)元素的集合分為若干個(gè)兩兩不交的子集，按照下述規(guī)則將某一個(gè)子集中某些元素挪到另一個(gè)子集：從前一子集挪到后一子集的元素個(gè)數(shù)等于后一子集的元素個(gè)數(shù)（前一子集的元素個(gè)數(shù)應(yīng)不小于后一子集的元素個(gè)數(shù)），證明：可以經(jīng)過有限次挪動(dòng)，使得到的子集與原集合相重合。分析：首先考慮到是一個(gè)很特殊的數(shù)，其次我們發(fā)現(xiàn)若兩個(gè)集合的元素個(gè)數(shù)除以2的若干次冪后若為奇數(shù)，那么，它們之間挪后就應(yīng)為偶數(shù)這一事實(shí)，若還不能想到解答就試一下，時(shí)的情況，相信解答就不會(huì)難找到了。證明：考慮含奇數(shù)個(gè)元素的子集（如果有這樣的子集），因?yàn)樗凶蛹?/p>

29、素的個(gè)數(shù)總和是偶數(shù)，所以具有奇數(shù)個(gè)元素的子集個(gè)數(shù)也是偶數(shù)，任意將所有含有奇數(shù)個(gè)元素的子集配成對(duì)，對(duì)每對(duì)子集按題目要求的規(guī)則移動(dòng)：從較大的子集挪出一些元素，添加到較小的子集，挪出的元素個(gè)數(shù)為較小子集的元素個(gè)數(shù)，于是得到的所有子集的元素個(gè)數(shù)都是偶數(shù)，現(xiàn)在考慮元素個(gè)數(shù)不被4整除的子集，如果，則總共有兩個(gè)元素，它們?cè)谕粋€(gè)子集，因此設(shè)，因?yàn)樽蛹脑貍€(gè)數(shù)的總數(shù)被4整除，因此這樣的子集的個(gè)數(shù)為偶數(shù)，任意將這樣的子集配成對(duì)，對(duì)每一對(duì)子集施行滿足題目要求的挪動(dòng)，于是得到的每個(gè)子集數(shù)均可被4整除，依此做下去，最后得到的每個(gè)子集元素個(gè)數(shù)均可被整除，也就是只能有一個(gè)子集，它的元素個(gè)數(shù)為，證畢。說明：這道題的證明中隱含了一種單一變量在變化時(shí)變化方向相同這一性質(zhì)，就這道題來說，一直在增加的就是各子集元素個(gè)數(shù)被2的多少次冪整除的這個(gè)冪次數(shù)，這是一