有一天，王小子在遨游世界時(shí)，遇到了一場(chǎng)自然災(zāi)害。一個(gè)人孤獨(dú)的在一個(gè)島上，沒(méi)有吃的沒(méi)有喝的。在他饑寒交迫將要死亡時(shí)，死神來(lái)了。由于這個(gè)死神在成神之前是一個(gè)數(shù)學(xué)家，所以他有一個(gè)習(xí)慣，會(huì)和即死之人玩一個(gè)數(shù)學(xué)游戲，來(lái)決定是否將其靈魂帶走。游戲規(guī)則是死神給王小子兩個(gè)整數(shù)n（100<=n<=1000000）,m(2<=m<=n)，在1~n個(gè)數(shù)中，隨機(jī)取m個(gè)數(shù),問(wèn)在這m個(gè)數(shù)中是否一定存在一個(gè)數(shù)是另一個(gè)數(shù)的倍數(shù)，是則回答“YES",否則”NO"。如果王小子回答正確，將有再活下去的機(jī)會(huì)。但是他很后悔以前沒(méi)有好好學(xué)習(xí)數(shù)學(xué)，王小子知道你數(shù)學(xué)學(xué)得不錯(cuò)，請(qǐng)你救他一命。

本題應(yīng)用的是鴿籠原理，也叫抽屜原理。

桌上有十個(gè)蘋(píng)果，要把這十個(gè)蘋(píng)果放到九個(gè)抽屜里，無(wú)論怎樣放，我們會(huì)發(fā)現(xiàn)至少會(huì)有一個(gè)抽屜里面放兩個(gè)蘋(píng)果。這一現(xiàn)象就是我們所說(shuō)的“抽屜原理”。?抽屜原理的一般含義為：“如果每個(gè)抽屜代表一個(gè)集合，每一個(gè)蘋(píng)果就可以代表一個(gè)元素，假如有n+1或多于n+1個(gè)元素放到n個(gè)集合中去，其中必定至少有一個(gè)集合里有兩個(gè)元素。”?抽屜原理有時(shí)也被稱(chēng)為鴿巢原理（“如果有五個(gè)鴿子籠，養(yǎng)鴿人養(yǎng)了6只鴿子，那么當(dāng)鴿子飛回籠中后，至少有一個(gè)籠子中裝有2只鴿子”）。它是組合數(shù)學(xué)中一個(gè)重要的原理。

AC碼：

鴿籠原理應(yīng)用：

1、從2、4、6、…、30這15個(gè)偶數(shù)中，至少任取幾個(gè)數(shù)，其中一定有兩個(gè)數(shù)之和是34？

???答案：?9

2、從1、2、3、4、…、19、20這20個(gè)自然數(shù)中，至少任選幾個(gè)數(shù)，就可以保證其中一定包括兩個(gè)數(shù)，它們的差是12？

???答案：13

3、?從1到20這20個(gè)數(shù)中，至少任取多少個(gè)數(shù)，必有兩個(gè)數(shù)，其中一個(gè)數(shù)是另一個(gè)數(shù)的倍數(shù)？

???答案：11

4、某校校慶，來(lái)了n位校友，彼此認(rèn)識(shí)的握手問(wèn)候.請(qǐng)你證明無(wú)論什么情況，在這n個(gè)校友中至少有兩人握手的次數(shù)一樣多？

???答案：共有n位校友，每個(gè)人握手的次數(shù)最少是0次，即這個(gè)人與其他校友都沒(méi)有握過(guò)手；最多有n-1次，即這個(gè)人與每位到會(huì)校友都握了手.然而，如果有一個(gè)校友握手的次數(shù)是0次，那么握手次數(shù)最多的不能多于n-2次；如果有一個(gè)校友握手的次數(shù)是n-1次，那么握手次數(shù)最少的不能少于1次.不管是前一種狀態(tài)0、1、2、…、n-2，還是后一種狀態(tài)1、2、3、…、n-1，握手次數(shù)都只有n-1種情況.把這n-1種情況看成n-1個(gè)抽屜，到會(huì)的n個(gè)校友每人按照其握手的次數(shù)歸入相應(yīng)的“抽屜”，根據(jù)抽屜原理，至少有兩個(gè)人屬于同一抽屜，則這兩個(gè)人握手的次數(shù)一樣多。

5、15個(gè)網(wǎng)球分成數(shù)量不同的4堆，數(shù)量最多的一堆至少有多少個(gè)球？

???答案：此題實(shí)際是求出15可分拆多少種4個(gè)互不相同的整數(shù)之和，而15=1+2+3+9=1+2+4+8=1+2+5+7=1+3+4+7=1+3+5+6=2+3+4+6，所以最多一堆的球數(shù)可能是9、8、7、6，其中至少有6個(gè)。

整除問(wèn)題

1、任取8個(gè)自然數(shù)，必有兩個(gè)數(shù)的差是7的倍數(shù)。

???解析：在與整除有關(guān)的問(wèn)題中有這樣的性質(zhì)，如果兩個(gè)整數(shù)a、b，它們除以自然數(shù)m的余數(shù)相同，那么它們的差a-b是m的倍數(shù).根據(jù)這個(gè)性質(zhì)，本題只需證明這8個(gè)自然數(shù)中有2個(gè)自然數(shù)，它們除以7的余數(shù)相同.我們可以把所有自然數(shù)按被7除所得的7種不同的余數(shù)0、1、2、3、4、5、6分成七類(lèi).也就是7個(gè)抽屜.任取8個(gè)自然數(shù)，根據(jù)抽屜原理，必有兩個(gè)數(shù)在同一個(gè)抽屜中，也就是它們除以7的余數(shù)相同，因此這兩個(gè)數(shù)的差一定是7的倍數(shù)。

2、對(duì)于任意的五個(gè)自然數(shù)，證明其中必有3個(gè)數(shù)的和能被3整除。

???解析：

3、任意給定7個(gè)不同的自然數(shù)，求證其中必有兩個(gè)整數(shù)，其和或差是10的倍數(shù).

???解析：注意到這些數(shù)除以10的余數(shù)即個(gè)位數(shù)字，以0，1，…，9為標(biāo)準(zhǔn)制造10個(gè)抽屜，標(biāo)以[0]，[1]，…，[9].若有兩數(shù)落入同一抽屜，其差是10的倍數(shù)，只是僅有7個(gè)自然數(shù)，似不便運(yùn)用抽屜原則，再作調(diào)整：[6]，[7]，[8]，[9]四個(gè)抽屜分別與[4]，[3]，[2]，[1]合并，則可保證至少有一個(gè)抽屜里有兩個(gè)數(shù)，它們的和或差是10的