全國

        熱門城市 | 全國 北京 上海 廣東

        華北地區 | 北京 天津 河北 山西 內蒙古

        東北地區 | 遼寧 吉林 黑龍江

        華東地區 | 上海 江蘇 浙江 安徽 福建 江西 山東

        華中地區 | 河南 湖北 湖南

        西南地區 | 重慶 四川 貴州 云南 西藏

        西北地區 | 陜西 甘肅 青海 寧夏 新疆

        華南地區 | 廣東 廣西 海南

        • 微 信
          高考

          關注高考網公眾號

          (www_gaokao_com)
          了解更多高考資訊

        首頁 > 高中頻道 > 競賽聯賽知識 > 抽屜原則

        抽屜原則

        2009-08-31 11:13:39網絡來源

        大家知道,兩個抽屜要放置三只蘋果,那么一定有兩只蘋果放在同一個抽屜里,更一般地說,只要被放置的蘋果數比抽屜數目大,就一定會有兩只或更多只的蘋果放進同一個抽屜,可不要小看這一簡單事實,它包含著一個重要而又十分基本的原則——抽屜原則.

        1.  抽屜原則有幾種最常見的形式

        原則1 如果把n+k(k≥1)個物體放進n只抽屜里,則至少有一只抽屜要放進兩個或更多個物體:

        原則本身十分淺顯,為了加深對它的認識,我們還是運用反證法給予證明;如果每個抽屜至多只能放進一個物體,那么物體的總數至多是n,而不是題設的n+k(k≥1),這不可能.

        原則雖簡單.巧妙地運用原則卻可十分便利地解決一些看上去相當復雜、甚至感到無從下手的總是,比如說,我們可以斷言在我國至少有兩個人出生的時間相差不超過4秒鐘,這是個驚人的結論,該是經過很多人的艱苦勞動,統計所得的吧!不,只須我們稍動手算一下:

        不妨假設人的壽命不超過4萬天(約110歲,超過這個年齡數的人為數甚少),則

        10億人口安排在8億6千4百萬個“抽屜”里,根據原則1,即知結論成立.

        下面我們再舉一個例子:
        例1  幼兒園買來了不少白兔、熊貓、長頸鹿塑料玩具,每個小朋友任意選擇兩件,那么不管怎樣挑選,在任意七個小朋友中總有兩個彼此選的玩具都相同,試說明道理.

        解 從三種玩具中挑選兩件,搭配方式只能是下面六種:

        (兔、兔),(兔、熊貓),(兔、長頸鹿),(熊貓、熊貓),(熊貓、長頸鹿),(長頸鹿、長頸鹿)

        把每種搭配方式看作一個抽屜,把7個小朋友看作物體,那么根據原則1,至少有兩個物體要放進同一個抽屜里,也就是說,至少兩人挑選玩具采用同一搭配方式,選的玩具相同.

        原則2 如果把mn+k(k≥1)個物體放進n個抽屜,則至少有一個抽屜至多放進m+1個物體.證明同原則相仿.若每個抽屜至多放進m個物體,那么n個抽屜至多放進mn個物體,與題設不符,故不可能.

        原則1可看作原則2的物例(m=1)

        例2正方體各面上涂上紅色或藍色的油漆(每面只涂一種色),證明正方體一定有三個面顏色相同.

        證明把兩種顏色當作兩個抽屜,把正方體六個面當作物體,那么6=2×2+2,根據原則二,至少有三個面涂上相同的顏色.

        例3 把1到10的自然數擺成一個圓圈,證明一定存在在個相鄰的數,它們的和數大于17.

        證明 如圖12-1,設a1,a2,a3,…,a9,a10分別代表不超過10的十個自然數,它們圍成一個圈,三個相鄰的數的組成是(a1,a2,a3),(a2,a3,a4),(a3,a4,a5),…,(a9,a10,a1),(a10,a1,a2)共十組.現把它們看作十個抽屜,每個抽屜的物體數是a1+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)

        根據原則2,至少有一個括號內的三數和不少于17,即至少有三個相鄰的數的和不小于17.

        原則1、原則2可歸結到期更一般形式:
        原則3把m1+m2+…+mn+k(k≥1)個物體放入n個抽屜里,那么或在第一個抽屜里至少放入m1+1個物體,或在第二個抽屜里至少放入m2+1個物體,……,或在第n個抽屜里至少放入mn+1個物體.

        證明假定第一個抽屜放入物體的數不超過m1個,第二個抽屜放入物體的數不超過m2個,……,第n個抽屜放入物體的個數不超過mn,那么放入所有抽屜的物體總數不超過m1+m2+…+mn個,與題設矛盾.

        例4 有紅襪2雙,白襪3雙,黑襪4雙,黃襪5雙,藍襪6雙(每雙襪子包裝在一起)若取出9雙,證明其中必有黑襪或黃襪2雙.

        證明 除可能取出紅襪、白襪3雙外.還至少從其它三種顏色的襪子里取出4雙,根據原理3,必在黑襪或黃襪、藍襪里取2雙.

        上面數例論證的似乎都是“存在”、“總有”、“至少有”的問題,不錯,這正是抽屜原則的主要作用.需要說明的是,運用抽屜原則只是肯定了“存在”、“總有”、“至少有”,卻不能確切地指出哪個抽屜里存在多少.

        2.  制造抽屜是運用原則的一大關鍵

        首先要指出的是,對于同一問題,常可依據情況,從不同角度設計抽屜,從而導致不同的制造抽屜的方式.

        例5 在邊長為1的正方形內,任意給定13個點,試證:其中必有4個點,以此4點為頂點的四邊開面積不超過(假定四點在一直線上構成面積為零的四邊形).

        證明如圖12-2把正方形分成四個相同的小正方形.

        因13=3×4+1,根據原則2,總有4點落在同一個小正方形內(或邊界上),以此4點為頂點的四邊形的面積不超過小正方形的面積,也就不超過整個正方形面積的.

        事實上,由于解決問題的核心在于將正方形分割成四個面積相等的部分,所以還可以把正方形按圖12-3(此處無圖)所示的形式分割.

        合理地制造抽屜必須建立在充分考慮問題自身特點的基礎上.

        例6 在一條筆直的馬路旁種樹,從起點起,每隔一米種一棵樹,如果把三塊“愛護樹木”的小牌分別掛在三棵樹上,那么不管怎樣掛,至少有兩棵掛牌的樹之間的距離是偶數(以米為單位),這是為什么?

        解如圖12-4(設掛牌的三棵樹依次為A、B、C.AB=a,BC=b,若a、b中有一為偶數,命題得證.否則a、b均為奇數,則AC=a+b為偶數,命題得證.

        下面我們換一個角度考慮:給每棵樹上編上號,于是兩棵樹之間的距離就是號碼差,由于樹的號碼只能為奇數和偶數兩類,那么掛牌的三棵樹號碼至少有兩個同為奇數或偶數,它們的差必為偶數,問題得證.

        后一證明十分巧妙,通過編號碼,將兩樹間距離轉化為號碼差.這種轉化的思想方法是一種非常重要的數學方法

        例7 從自然數1,2,3,…99,100這100個數中隨意取出51個數來,求證:其中一定有兩個數,,它們中的一個是另一個的倍數.

        分析設法制造抽屜:(1)不超過50個;(2)每個抽屜的里的數(除僅有的一個外),其中一個數是另一個數的倍數,一個自然數的想法是從數的質因數表示形式入手.

        解設第一個抽屜里放進數:1,1×2,1×22,1×23,1×24,1×25,1×26

        第二個抽屜時放進數:3,3×2,3×22,3×23,3×24,3×25

        第三個抽屜里放進數:5,5×2,5×22,5×23,5×24

        ………………

        第二十五個抽屜里放進數:49,49×2;

        第二十六個抽屜里放進數:51.

        ………………

        第五十個抽屜里放進數:99.

        那么隨意取出51個數中,必有兩個數同屬一個抽屜,其中一個數是另一個數的倍數.

        制造抽屜并非總是一帆風順的,有時要邊制造邊調整、改進.

        例8 任意給定7個不同的自然數,求證其中必有兩個整數,其和或差是10的倍數.

        分析注意到這些數隊以10的余數即個位數字,以0,1,…,9為標準制造10個抽屜,標以[0],[1],…,[9].若有兩數落入同一抽屜,其差是10的倍數,只是僅有7個自然數,似不便運用抽屜原則,再作調整:[6],[7],[8],[9]四個抽屜分別與[4],[3],[2],[1]合并,則可保證至少有一個抽屜里有兩個數,它們的和或差是10的倍數.

        3.  較復雜的問題須反復地運用抽屜原則,將復雜問題轉化為簡單問題.

        例9以(x,y,z)表示三元有序整數組,其中x、y、z為整數,試證:在任意七個三元整數組中,至少有兩個三元數組,它們的x、y、z元中有兩對都是奇數或都是偶數.

        分析 設七個三元素組為A1(x1,y1,z1)、A2(x2,y2,z2)、…、A7(x7,y7,z7).現在逐步探索,從x元開始,由抽屜原則,x1,x2,…,x7這七個數中,必定有四個數具有相同的奇偶性,不妨設這四個數是x1,x2,x3,x4且為偶數,接著集中考慮A1、A2、A3、A4這四組數的y元,若比如y1,y2,y3,y4中有兩個是偶數,則問題已證,否則至多有一個是偶數,比如y4是偶數,這時我們再來集中考慮A1、A2、A3的z元.在z1,z2,z3中,由抽屜原則必有兩個數具有相同的奇偶性,如z1、z2,這時無論它們是奇數,還是偶數,問題都已得到證明.

        下面介紹一個著名問題.

        例10 任選6人,試證其中必有3人,他們互相認識或都不認識.

        分析 用A、B、C、D、E、F表示這6個人,首先以A為中心考慮,他與另外五個人B、C、D、E、F只有兩種可能的關系:認識或不認識,那么由抽屜原則,他必定與其中某三人認識或不認識,現不妨設A認識B、C、D三人,當B、C、D三人都互不認識時,問題得證;當B、C、D三人中有兩人認識,如B、C認識時,則A、B、C互相認識,問題也得證.

        本例和上例都采用了舍去保留、化繁為簡、逐步縮小考慮范圍的方法.

        例11a,b,c,d為四個任意給定的整數,求證:以下六個差數

        b-a,c-a,d-a,c-b,d-b,d-c的乘積一定可以被12整除.

        證明  把這6個差數的乘積記為p,我們必須且只須證明:3與4都可以整除p,以下分兩步進行.

        第一步,把a,b,c,d按以3為除數的余數來分類,這樣的類只有三個,故知a,b,c,d中至少有2個除以3的余數相同,例如,不妨設為a,b,這時3可整除b-a,從而3可整除p.

        第二步,再把a,b,c,d按以4為除數的余數來分類,這種類至多只有四個,如果a,b,c,d中有二數除以4的余數相同,那么與第一步類似,我們立即可作出4可整除p的結論.

        設a,b,c,d四數除以4的余數不同,由此推知,a,b,c,d之中必有二個奇數(不妨設為a,b),也必有二個偶數(設為c,d),這時b-a為偶數,d-c也是偶數,故4可整除(b-a)(d-c),自然也可得出4可整除p.

        如果能進一步靈活運用原則,不僅制造抽屜,還根據問題的特征,制造出放進抽屜的物體,則更可收到意想不到的效果.

        例12 求證:從任意n個自然數a1,a2,…,an中可以找到若干個數,使它們的和是n的倍數.

        分析以0,1,…,n-1即被n除的余數分類制造抽屜的合理的,但把什么樣的數作為抽屜里的物體呢?扣住“和”,構造下列和數:

        S1=a1,

        S2=a1+a2,

        S=a1+a2+a3,

        …………

        Sn=a1+a2+…+an

        其中任意兩個和數之差仍為和數,若他們之中有一是n的倍數,問題得證,否則至少有兩個數被n除余數相同,則它們的差即它們中若干數(包括1個)的和是n的倍數,問題同樣得證.

        例子3(北京1990年高一競賽)910瓶紅、藍墨水,排成130行,每行7瓶,證明:不論怎樣排列,紅藍墨水瓶的顏色次序必定出現下述兩種情況之一種:

        (1)至少有三行完全相同;

        (2)至少有兩組(四行)每組的兩行完全相同.

        解910瓶紅、藍墨水排成130行,每行7瓶,對一行來說,每個位置上有紅藍兩種可能,因此,一行的紅、藍墨水排法有27=128種,對每一種不同排法設為一種“行式”,共有128種行式.

        現有130行,在其中任取129行,依抽屜原則知,必有兩行A、B行式相同.

        除A、B外余下128行,若有一行P與A行式相同,知滿足(1)至少有三行A、B、P完全相同,若在這128行中設直一行5A行或相同,那么這128行至多有127種行式,依抽屜原則,必有兩行C、D具有相同行式,這樣便找到了(A、B),(C、D)兩組(四行),且兩組兩行完全相同.

        練習十二

        1.  一個籃球運動員在15分鐘內將球投進籃圈20次,證明總有某一分鐘他至少投進兩次.

        2.  有黑、白、黃筷子各8只,不用眼睛看,任意地取出筷子來,使得至少有兩雙筷子不同色,那么至少要取出多少只筷子才能做到?

        3.  證明:在1,2,3,…,10這十個數中任取六個數,那么這六個數中總可以找到兩個數,其中一個是另一個的倍數.

        4.  證明:任意502個整數中,必有兩個整數的和或差是998的倍數.

        5.  任意寫一個由數字1,2,3組成的30位數,從這30位數任意截取相鄰三位,可得一個三位數,證明:在從各個不同位置上截得的三位數中至少有兩個相等.

        6.  證明:把任意10個自然數用適當的運算符號連接起來,運算的結果總能被1890整除.

        7.  七條直線兩兩相交,所得的角中至少有一個角小于26°.

        8.  用2種顏色涂3行9列共27個小方格,證明:不論如何涂色,其中必至少有兩列,它們的涂色方式相同.

        9.  用2種顏色涂5×5共25個小方格,證明:必有一個四角同色的矩形出現.

        10.              求證存在形如11…11的一個數,此數是1987的倍數.

         

        練習十二

        1.15分鐘里在每一分鐘看作一個抽屜,20次投籃看作20個物體,根據原理一即得.

        2.至少要取11只筷子.因為11只筷子中必有一雙筷子同色,不妨設它是黃色,則黑色或白色的筷子至少有3只,其中必有一雙同色,即黑色或白色,故取11只筷子足以保證成功.但少于11只不行,如取10只筷子,閔可能出現8只黃色,黑白各一只,不合要求.

        3.將10個數分成5組:(1,7),(2,6),(3,9),(4,8),(5,10).任取六個數必有兩個落入同一組,而同組二數中一數是另一數的倍數.

        4.每個整數被998除,余數必是0,1,2,…,997中的一個.把這998個余數制造為(0),(1,997),(2,996),…,(497,501),(498),(499),(500)共501個抽屜,把502個整數按被998除的余數大小分別放入上述抽屜,必有兩數進入同一抽屜.若余數相同,那么它們的差是998的倍數,否則和為998的倍數.

        5.從各種位置上截得的三位數有28個,但由1,2,3組成的不同三位數有3×3×3=27個,故有兩個截得的三位數相同.

        6.1890=2×3×5×7×9.將10個數記為x,x,…,x,x10.10個數中至少有兩個被9除余數相同,設為x,x則x-x可被9整除.同樣剩下8個數中有兩個數的差可被7整除,記為x-x­,剩下6個數中有兩個數的差可被5整除,記為x-x,剩下4個數中有兩個數的差可被3整除,記為x-x.剩下兩數x,x10,若有一數為偶數,則x,x10可被2整除,否則x-x10可被2整除.故乘積(x-x)(x-x)(x-x)(x-x)x·x10與(x-x)(x-x)(x-x)(x-x)(x-x10)二者之一必可被1890整除.

        7.任選一點P,過P點分別作各線的平行線,則它們把一周角分成14個彼此相鄰的角,其中至少有一個角小于26°.

        8.用兩種顏色涂1×3的小方格共有8種方法.現有9列,由抽屜原則,必有兩列涂法一樣.

        9.設兩種顏色為紅、藍,考察第一行的涂色.必有三格同色,不妨設為紅色,且在左邊三列.現考察左邊三列,若下面四行中某一行有兩格同為紅色,則出現四角同紅色矩形,否則每行僅可能一格染紅色,從而四行中必有二行左邊三列中有兩列同染藍色,從而得到四角同為藍色的矩形.

        10.考慮1,11,…共1987個數,其中必有一個是1987的倍數,否則必有兩數被1987除余數相同,其差

        是1987的倍數.但10與1987沒有除1外的因數,故是1987倍數導致矛盾.

         

        [標簽:數的整除 推理與證明 倍數 約數倍數]

        分享:

        高考院校庫(挑大學·選專業,一步到位!)

        高考院校庫(挑大學·選專業,一步到位!)

        高校分數線

        專業分數線

        • 歡迎掃描二維碼
          關注高考網微信
          ID:gaokao_com

        • 👇掃描免費領
          近十年高考真題匯總
          備考、選科和專業解讀
          關注高考網官方服務號


        主站蜘蛛池模板: 欧美疯狂做受xxxxx高潮| 视频一区在线免费观看| 男人黄女人色视频在线观看| 思思久而久焦人| 亚洲av无码专区在线观看下载 | 国产高清在线精品一区二区三区| 一区二区三区四区视频| 手机在线色视频| 久久久夜间小视频| 日韩欧美中文字幕一区| 亚洲中文字幕久久精品无码喷水 | 小婷的性放荡日记h交| 中文字幕无码精品三级在线电影| 日本牲交大片无遮挡| 久草福利资源网站免费| 欧美两性人xxxx高清免费| 亚洲欧美色一区二区三区| 狠狠躁夜夜躁人人爽天天天天97| 内射中出日韩无国产剧情| 美女在线免费观看| 国产AV一区二区三区传媒| 韩日午夜在线资源一区二区| 国产成人精品日本亚洲专区6| 亚洲欧美日韩精品中文乱码| 国产精品伦理一二三区伦理| 51视频精品全部免费最新| 国产高清在线精品免费软件| 97无码人妻福利免费公开在线视频 | 午夜爽爽爽男女污污污网站| 老妇激情毛片免费| 国产一区二区三区日韩欧美| 达达兔午夜起神影院在线观看麻烦 | 欧美大BBBBBBBBBBBB| 亚洲国产高清视频在线观看| 欧美综合第一页| 亚洲欧美乱综合图片区小说区 | 人妻少妇一区二区三区| 男人插女人app| 免费大片黄在线观看| 粗大的内捧猛烈进出在线视频| 免费看特级毛片|