抽屜原理與存在性問題

第四講抽屜原理與存在性問題Q本講概述本講我們將講述組合數(shù)學中一個非常簡單卻又十分重要，應(yīng)用十分廣泛的一個原理，即抽屜原理.然后我們將給出與抽屜原理內(nèi)涵相通的幾個變形，即平均值原理與圖形重疊原理事實上這幾個原理是用來證明存在性問題的有力工具之一，當然我們還可以利用極端原理、反證法、數(shù)學歸納法、算兩次、計數(shù)方法和構(gòu)造法等等來加以證明.本講我們主要講述利用平均值原理（其在整數(shù)和圖形范圍內(nèi)的形式分別為抽屜原理和圖形重疊原理）來證明存在性問題，并略舉數(shù)例說明其它方法在證明存在性問題中的應(yīng)用.m—1 一第一抽屜原理：若將m個物件放入n個抽屜中，則必有一個抽屜內(nèi)至少有［ ］+1個物件.nm第二抽屜原理：若將m個物件放入n個抽屜中，則必有一個抽屜內(nèi)至多有［一］個物件.n事實上這兩個原理利用極端性原理與反證法極易證明，此處從略.平均值原理1：設(shè)a,a，…,a為實數(shù)，且A="1*氣+…+氣，則a,a，…,a中必有一個不小于A，1 2n n 12n也必有一個不大于A平均值原理2：設(shè)a,a，…,a為正實數(shù)，且G=Ja-a-...-a，則a,a，…,a中必有一個不小于G，1 2n 1 2n 1 2n也必有一個不大于G圖形重疊原理：把面積為￡,%,...,5計的n個平面圖形以任意方式放入一個面積為S的平面圖形A內(nèi)，（1） 如果*+S2+...+S>S，則必有兩個圖形有公共點；（2） 如果S+S+...+S<S，則必有一點不屬于上述n個圖形中任意一個12 n可以發(fā)現(xiàn)，上述三組原理都是極端性原則在不同場合的具體表現(xiàn)形式.極端性法則是處理組合數(shù)學中存在性的利器，通過對這三組原理及其解題技巧的深刻把握，我們也可以自己創(chuàng)造一些類似的極端性原理來解決問題.一般來說，適合應(yīng)用抽屜原理解決的數(shù)學問題具有如下特征：新給的元素具有任意性.如n+1個蘋果放入n個抽屜，可以隨意地一個抽屜放幾個，也可以讓抽屜空著.問題的結(jié)論是存在性命題，題目中常含有“至少有......”、“一定有......”、"不少于......”、"存在......”、"必然有......”等詞語，其結(jié)論只要存在，不必確定，即不需要知道第幾個抽屜放多少個蘋果.用抽屜原理解題的基本思想是根據(jù)問題的自身特點和本質(zhì)，弄清對哪些元素進行分類，找出分類的規(guī)律.關(guān)鍵是構(gòu)造適合的抽屜，抽屜之間可以有公共部分，亦可以沒有公共部分。一般說來，數(shù)的奇偶性、剩余類、數(shù)的分組、染色、線段與平面圖形的劃分等，都可作為構(gòu)造抽屜的依據(jù)。這一簡單的思維方式在解題過程中卻可以演變出很多奇妙的變化和頗具匠心的運用。抽屜原理常常結(jié)合幾何、整除、數(shù)列和染色等問題出現(xiàn)，從小學奧數(shù)、中學奧數(shù)、IMO到Putnam都可以見到它的身影。實際應(yīng)用中，抽屜原理常常與反證法結(jié)合在一起。教師備注：本節(jié)題目有些可能學生在初中接觸過，教師可以適當選擇其中較有新意的問題利用抽屜原理解題的關(guān)鍵是根據(jù)題目特點巧妙地構(gòu)造“抽屜”：將題目中涉及元素按照某一性質(zhì)分類，當取出足夠多的元素時，即可斷言必有某些元素屬于同一個“抽屜”.構(gòu)造抽屜的常用方法有：劃分集合、分割圖形、利用剩余類等等.與抽屜原理相關(guān)的試題中，聯(lián)賽中的題目往往利用抽屜原理是解題的關(guān)鍵，但在冬令營級別的賽題中，往往抽屜原理只是其中的一小步或者利用它解決其中的小塊問題而已【例1】將平面上的每個點都以紅、藍兩色之一著色，證明：存在這樣兩個相似的三角形，它們的相似比為1995，并且每一個三角形的三個頂點同色?！纠?】在任意給出的100個整數(shù)中，都可以找出若干個數(shù)來(可以是一個數(shù))它們的和可被100整除。【例3】從1-100的自然數(shù)中，任意取出51個數(shù)，證明其中一定有兩個數(shù)，它們中的一個是另一個的整數(shù)倍.【例4】任給7個實數(shù)，證明其中必有兩個數(shù)，記為X,J，滿足0<X——.1+x—3【例5】給一個由10個互不相等的兩位十進制正整數(shù)組成的集合。求證：這個集合必有兩個無公共元素的非空子集合，各子集合中各數(shù)之和相等.【例6】試求最小的正整數(shù)名使得對于任何n個連續(xù)正整數(shù)中，必有一數(shù)，其各位數(shù)字之和是7的倍數(shù).【例7】從前25個自然數(shù)中任意取出7個數(shù)，證明：取出的數(shù)中一定有兩個數(shù)，這兩個數(shù)中大數(shù)不超過小數(shù)的1.5倍.【例8】(1)任選6人，試證其中必有3人，他們互相認識或都不認識.(2)17名科學家中每兩名科學家都和其他科學家通信，在他們通信時，只討論三個題目，而且任意兩名科學家通信時只討論一個題目，證明：其中至少有三名科學家，他們相互通信時討論的是同一個題目?！纠?】任意給定10個自然數(shù)，試證明：可以用減，乘兩種運算以及括號將它們適當連結(jié)起來，其結(jié)果可被1890整除.【例10】n支球隊要舉行主客場雙循環(huán)比賽（每兩支球隊比賽兩場，各有一場主場比賽），每支球隊在一周（從周日到周六的七天）內(nèi)可以進行多場客場比賽。但如果某周內(nèi)該球隊有主場比賽，在這一周內(nèi)不能安排該球隊的客場比賽。如果4周內(nèi)能夠完成全部比賽，求n的最大值。【例11】從4個同心圓的圓心出發(fā)的100條射線等分各圓周，分別與4個圓各有100個交點，任意給每個圓上的點染上黑白兩色之一，使每個圓上都恰有50個黑點和50個白點，證明：可將此4個圓適當旋轉(zhuǎn)，使這100條射線中至少存在13條射線，它們中每一條穿過的4個點顏色都相同.Q大顯身手1.把1到10的自然數(shù)擺成一個圓圈，證明一定存在3個相鄰的數(shù)，它們的和數(shù)大于17.2.在邊長為1的等邊三角形內(nèi)（包括邊界）有任意五個點。證明：至少有兩個點之間的距離不大于12■3.a，b，c，d為四個任意給定的整數(shù)，求證：以下六個差數(shù)b-a，c-a，d-a，c-b，d-b，d-c的乘積一定可以被12整除.4. 平面上任作8條直線，互不平行，證明其中必有兩條直線的夾角2305. 15個人圍著圓桌坐下，圓桌上有15個人的名牌，但是大家是隨意坐的，坐下以后才發(fā)現(xiàn)沒有一個人與桌上的名牌相對應(yīng)，證明：可以轉(zhuǎn)動圓桌，使得至少兩個人與他們的名牌相符6.平面上有兩個定點A和B及任意四點P,P,P,P,求證：這四點中一定有兩點P,P1 2 3 4 ij(i,j=1,2,3,4,i豐j)使得|sinZAPB-sinZAPB\<|。7.一個車間有一條生產(chǎn)流水線，