數(shù)林外傳系列典藏版03抽屜原則

千里之行，始于足下朽木易折，金石可鏤Word-可編輯1第一堂算術(shù)課新學(xué)年開始了.開學(xué)的那一天,紅星小學(xué)一年級一班第一堂就是算術(shù)課.任課的張教師是一-位很有經(jīng)驗、很有水平的老教師.她講課深入淺出,活潑生動,凡是持久聽張教師講課的學(xué)生,總是不知不覺地對數(shù)學(xué)產(chǎn)生了濃厚的興趣.張教師走進課堂,全班學(xué)生起立,向這位辛勤的園丁致敬.環(huán)視那幾十張陌生而可愛的小臉,張教師心里彌漫了無限的喜悅.她用容易而誠摯的語言向新學(xué)生表示祝賀和歡迎,接著說道:“我校今年招收了370名一年級新生,他們都年滿六歲但還不到七歲.我說呀,這么多的新學(xué)生中間,一定有兩個人是同年、同月、同日出生的.小學(xué)生們,你們說對不對?”對這個清新的結(jié)論,大家感到有趣而又驚訝,學(xué)生們低聲地互相議論起來.“張教師知道我們每一個人的生日了嗎?”“不會的,她今天同我們才頭一次見面,連我們的名字恐怕都叫不上來.”“"“張教師一定查看過我們的報名記下表了!”這一句話恰巧被張教師聞聲了,她笑著說:“我沒有看過你們的記下表,而且,徹低不須要看這些表,就可以得出這個結(jié)論."學(xué)生們更神奇了!張教師接著說:“學(xué)生們想想看,把十只蘋果放到九個抽屜中去,無論怎么放,這九個抽屜中一定有一個抽屜里放了兩只或兩只以上的蘋果.你們說對嗎?"“對!對!”學(xué)生們齊聲回答.小朋友所具備的常識,就足以使他們明了:要是每個抽屜中最多惟獨一只蘋果的話,那么九個抽屜至多才裝著九只蘋果.“好!我們把一年中的365天(閏年366天)的每一天看成一個'抽屜',而把370個新學(xué)生中的每一個人看成一只'蘋果',按照'蘋果'出生的日子,把它們放到對應(yīng)的'抽屜'中去.因為'蘋果'的數(shù)目多于''抽屜'的數(shù)目,就能知道:一定有一個'抽屜'中至少放著兩只'蘋果'.這就是說,至少有兩個學(xué)生的生日相同.再按照學(xué)生們的年齡的差別不超過一歲,所以,這兩個學(xué)生一定是同年、同月、同日出生的了.”小朋友們恍然大悟,會心地笑了.2三個原則運用第1節(jié)中采用過的推理主意,我們還可以證實如下越發(fā)令人驚訝的結(jié)論.按照常識,一個人的頭發(fā)的根數(shù)不會超過20萬.因此,在一個擁有20多萬人口的城市中,一定有那么兩個人,他們的頭發(fā)的根數(shù)相同.推理主意如下:我們設(shè)置200001個“抽屜”,并且對每一個“抽屜”依次標上頁碼0,1,2,3,?,200000.按各人頭上頭發(fā)的根數(shù)把人歸人相應(yīng)的一個“抽屜”.比如,倘若張樂平先生畫的三毛生活在這個城市,那么他就被歸為標有號碼“3”的那個“抽屜”.我們沒有理由排除這個城市中有留著光頭的人,所以必須設(shè)置““”號“抽屜”.因為人的數(shù)目多于“抽屜”的數(shù)目,故可以斷定,一定至少有兩個人與同一“抽屜”相對應(yīng),這兩個人天然就有同樣多根頭發(fā)了.容易看到,從本質(zhì)上來說,這依然是前一節(jié)中“十只蘋果”和“九個抽屜”的推理主意.這種推理的準確性,“顯然”連小學(xué)一年級的學(xué)生也能徹低采納.倘若把這種推理推廣到越發(fā)普通的形式,其準確性也徹低可以被不具備多少數(shù)學(xué)知識的人所認識.怎樣把這種推理推廣到普通形式呢?我們來擔(dān)心以下兩點:(1)倘若將“蘋果”換成“皮球”、鉛筆”或“數(shù)”,同時將“抽屜”相應(yīng)地換成“袋子”、“文具盒”或“數(shù)的集合”,那么依然可以得出相同的結(jié)論.這就是說:推理的準確性與詳細的對象沒有關(guān)系.我們把一切可以同“蘋果”互換的對象稱為“元素”，而把一切可以同“抽果”互換的對象稱為“集合”,從而得知:十個元素以隨意的方式歸入九個集合之中,那么其中一定有一個集合中至少包含兩個元素.(2)“蘋果”和“抽屜”的詳細數(shù)目是無關(guān)緊要的,只要蘋果(元素)的個數(shù)比抽屜(集合)的個數(shù)多,那么推理照樣成立.于是,我們就可以把“十只蘋果”和“九個抽屜”的推理主意推廣到下述的普通形式:原則1 把多于n個的元素按任一決定的方式分成n個集合,那么一定有一個集合中含有兩個或兩個以上的元素.原則1還有以下越發(fā)普通的形式:原則2 把多于m×n個的元素按任一決定的方式分成n個集合,那么一定有一個集合中含有m+1個或m這是很顯然的,因為若每個集合中所含元素的數(shù)目均不超過m,則這n個集合所含元素的個數(shù)就不會超過m×原則3 把無窮個元素按任一決定的方式分成有窮個集合,那么至少有一個集合中仍含無窮多個元素.這也是很顯然的,這是因為,倘若每個集合中只含有窮多個元素,那么有窮個集合只能包含有窮個元素.以上三個原則都稱為抽屜原則.看上去,它們都是異常容易的.可是,正是這樣一些很容易的原則,在初等數(shù)學(xué)乃至高等數(shù)學(xué)中,有著許多應(yīng)用.巧妙地運用這些原則,可以很順利地解決一些看上去相當(dāng)復(fù)雜、甚至覺得簡直無從下手的數(shù)學(xué)題目.3容易例子在本節(jié),我們運用抽屜原則來證實初等數(shù)學(xué)中的一些題目.【例1】在邊長為1的正方形內(nèi)隨意放置五個點.求證：其中必有兩個點,它們之間的距離不大于22證實 將這個正方形的兩對對邊上的中點銜接起來,把它分成四個大小相等的小正方形(圖3.1).在大正方形里任放五個點,就相當(dāng)于把五個點以任一決定的方式投放在這四個小正方形中.這里，我們把每一個小正方形看成一個“抽屜“,于是問題就歸結(jié)為把五個元素(點)放人四個“抽屜”(小正方形).按照前一節(jié)的原則1,必有一個小正方形,其中包含兩個或兩個以上的點,對其中的兩個點,它們之間的距離不會超過小正方形對角線的長度(即大正方形對角線長度的一半),即不大于22【例2】空間中有六個點,其中任何三點都不共線,任何四點都不共面.在每兩點之間連起直線段之后,將每一條這樣的線段或涂上紅色,或涂上藍色.求證:不論如何涂色,一定存在一個三角形,它的三條邊有相同的色彩.證實 從任一點出發(fā)到其余五個點,共可連五條線段.因為這五條線段已被紅、藍兩種色彩所涂染,倘若把紅線段分人一個“抽屜”,藍線段分人另一個“抽屜”,于是問題就歸結(jié)為五個元素(線段),即多于2×2個元素,分到兩個“抽屜”(藍色或紅色).按照原則2,其中至少有三條線段被分人同一個“抽屜”,即染有相同的色彩,例如說是紅色(圖3.2中的實線).我們來考察這三條由同一點出發(fā)、具有相同色彩的線段.把這三條線段的另外三個端點兩兩銜接起來,就構(gòu)成了圖3.2所示的虛線三角形.倘若有一條虛線被涂成紅色,那么它就與兩條實線組成一個紅邊三角形;倘若這三條虛線中一條紅邊也沒有,那么它們本身就組成一個藍邊三角形了.【例3】在邊長為1的正方形中,隨意放人九個點.證實:在以這些點為頂點的許許多多三角形中,必有一個三角形,它的面積不超過18.(1963年北京市數(shù)學(xué)比賽試題證實 用三條平行于上下底邊的直線，把正方形分成四個大小相等的長方形.九個點隨意放人這四個長方形中,按照原則2,即多于2×4個點放人四個長方形中,則至少有2+1個點(即3個點)落在某一個長方形之內(nèi).現(xiàn)在,異常取出這個長方形來加以研究(圖3.3).把落在這個長方形中的三點記為A,B,C,通過這三點分離作平行于底邊的直線ΔABC的面積=ΔAA'B這樣就得到了需要證實的結(jié)論.【例4】一個正方形被分成了15×15=225個大小相同的小方格(圖3.4),在每一個小方格中,隨意填寫1,2,3,?,55,56中的一個數(shù).求證:一定能夠找到四個小方格,它們的中央構(gòu)成一個平行四邊形的四個頂點,并且此平行四邊形的各條對角線兩端的兩個小方格中的數(shù)字之和相等.證實 因為15是一個奇數(shù),所以一定有一個小方格處在大正方形的中央位置,我們把它稱為“中央小方格”,在圖3.4中用黑塊標出.把關(guān)于中央小方格為中央對稱的每兩個小方格配成一對.這樣,便把除去中央小方格之外的224個小方格配成了112對.在任一對這種小方格中,令x表示其中一個小方格中所放的數(shù),x*表示其對稱的另一小方格中所放的數(shù).由假設(shè),1因此2這就是說,任何一對小方格中的兩數(shù)之和不外乎2,3,4,?,110,111,112這111種可能.但是,我們共有112對小方格.按照原則1,必至少有兩對小方格,使得各對中兩數(shù)之和為同一數(shù)字.每對小方格的中央的連線,倘若它們不重合的話,必在中央小方格的中央處互相平分.所以這時四個小方格的中央是一個平行四邊形的四個頂點.把連線互相重合的情形看做是一個退化了的平行四邊形,可以認為,在這種情況下,結(jié)論依然是準確的.【例5】從正整數(shù)擴散1234?99100,隨意選出51個數(shù)來.證實 首先注重,一個正整數(shù)要么本身是一個奇數(shù),要么是一個偶數(shù).若是一個偶數(shù),則經(jīng)過反復(fù)地提取因數(shù)“2”,一個正整數(shù)最后總能表示為“奇數(shù)×2l?l=123?16=8×2=4×24=12×2=6×倘若容許l=0,那么奇數(shù)也被包括在上述普通形式之中現(xiàn)在,把1到100的所有整數(shù)分成下面的50個集合:MMMM?MM?,M很顯然,1,2,?,100這100個整數(shù)沒有遺漏地被放人了這50個集合,并且,同一個數(shù)字絕不會浮上在兩個不同的集合中（讀者可自行證實這一結(jié)論）.因此,不論用何種方式從中取出51個數(shù),必然至少有兩個數(shù)是出自同一個集合的,而同一集合中的兩數(shù),大數(shù)必然是小數(shù)的整倍數(shù).【例6】一群人參加一個晚會,認識的朋友見面,總是要握手問好.求證:不論在何種情形下,必有兩個人,他們握手的次數(shù)是一樣多的(假定不同的兩人至多握手一次).證實 可以設(shè)參加晚會的人數(shù)為n.按照各人握手的次數(shù),便可將這些人分為n個類:A0,A1,?,An-1,其中Ai表示由恰好握過i次手的人組成的集合.很天然地會想到把這n個類看成“抽屜”,而把每一個人看成一個“蘋果”.但是,這里浮上了多少有點異常的情況:蘋果的數(shù)目與抽屜的數(shù)目竟是相等的,因此不能直接應(yīng)用抽屜原則.這就需要進一步的分析.稍加注重,就可以看出集合A0與An-1中必有一個是空集.這是因為若A0不是空集,表示至少有一個人同誰也沒有握過手,因此所有的人至多只能握過n-2次手,這表明An-【例7】一次圍棋大賽先后舉行了11個星期.有一位圍棋新秀,他的戰(zhàn)績是:每日至少勝1次,每星期最多勝12次.由此記錄一定可以推知:在一段延續(xù)的日子里,這位圍棋新秀不多不少地正巧勝了21次.證實 這一結(jié)論似乎有點出奇.但是,若你細讀了下述證實,便會對此結(jié)論深信不疑了.11個星期共有77天.用si表示從第1天至第i(i=1,2,?,77)1?s再令t易見22?由此可見,s1,s2,?,s77及t1,t2,?,t77這2×77=154個正整數(shù)落在1～153的范圍內(nèi),因此必有兩個數(shù)是相等的.顯然,t1,t【例8】從1,4,7,10,?,97,100這些數(shù)中,任取20個不同的整數(shù)形成一個集合A.求證:A中必有兩組不同的數(shù),其和都是104.證實 給定的數(shù)共有34個,相鄰的兩個數(shù)相差3.我們把這些數(shù)分成18個不相交的集合:1當(dāng)我們從給定的數(shù)中隨意地取出20個整數(shù)時,即使1,52這兩個數(shù)都在A中,A中也有余下的18個數(shù)分布在后面的那16個集合之中.于是至少有不同的兩個集合中的數(shù)也屬于A,此兩組數(shù)不相同,但每組數(shù)中的兩數(shù)之和都是104.證畢.在講述以下例子之前,回顧一下解題的經(jīng)驗是很有啟發(fā)的.“抽屜原則”本身并不難理解,在以上幾題的解題過程中也沒實用到任何高深的知識,但是,解題時需要相當(dāng)靈便的技巧.最關(guān)鍵的一步是“發(fā)明抽屜”,這不但要求人們具備代數(shù)、幾何、數(shù)論、組合的豐盛知識,更需要人們思維靈巧、靈便.拿例1來說吧,倘若用正方形的兩條對角線把它分為四個全等的等腰直角三角形(圖3.5),把其中的每個三角形當(dāng)成一個“抽屜”,雖仍可斷言五個點中必然至少有兩點落在同一個三角形之上,但是無法作出它們之間的距離不超過22的結(jié)論.下面要談的例子難度又進一步,難就難在如何恰當(dāng)?shù)卦O(shè)計抽屜.讀者應(yīng)該仔細體味,讓自己逐漸成為發(fā)明圖3.5【例9】在半徑為1的圓盤上隨意放置七個點,這里所謂的圓盤,包括圓周及圓的內(nèi)部.若這七個點中隨意兩點的距離都不小于1,則其中有一點為圓心.證實 設(shè)這個圓的中央為O,用直徑A1A4,令S1=扇形A1S2=扇形A2……S6=扇形A6OA1但不含線段OA1.很顯然,除圓心O之外,圓盤上的任一點都屬于而且僅屬于某一個Si事實上,這七個點的位置,在不計較繞圓心的任何旋轉(zhuǎn)之下,是唯一決定的.因為已證有一點必在圓心,其余六個點與中央的距離不小于1,所以它們必在圓周上.再加上這六個點互相間的距離不小于1,可知這六個點必須勻稱地分布在圓周上.【例10】平面上有1987個點,其中任何三點中都有兩點,它們之間的距離小于1.求證:存在一個半徑為1的圓,它至少蓋住這1987個點中的994個點.證實 大家應(yīng)該注重到,994的2倍正巧比1987多1.因此,我們只需根據(jù)條件能證實:可以作出兩個半徑為1的圓把這1987個點所有蓋住,那么就證得所需的結(jié)論了.在給定的1987個點中,任取一個點,記為A,以A為中央、以1為半徑作圓,這個圓叫做圓A.倘若圓A已經(jīng)蓋住了所有的1987個點,那么問題已經(jīng)得證.因此設(shè)給定的點中有一個點,記為B,不在圓A內(nèi).以B為中央、以1為半徑作圓,叫做圓B.下面我們來證實,圓A和圓B合并起來就已經(jīng)蓋住了給定的1987個點.倘若這一結(jié)論不準確,就是說,其中至少有一點,記為C,既不在圓A內(nèi)又不在圓B內(nèi),即有AC?1且.BC?1.但又已知AB?1(因為B不在圓A內(nèi)),因此A,B,C三點中,任何兩點間的距離均不小于1,這與假設(shè)矛盾.現(xiàn)在已經(jīng)確認,給定的1987個點中的每一個點,或者落在圓A內(nèi),或者落在圓B例10表明:“抽屜”的設(shè)置可以有很大的隨意性,而且這種設(shè)置是浮上在證實的過程之中的,而不是在開始一下子就能被看得出.【例11】有21個點在一個邊長為12的正三角形ABC中.證實:用一個半徑為3的圓盤總可以至少蓋住三個上述的點.證實 把ΔABC的每一條邊四等分,過這些分點作平行于各邊的直線,將ΔABC分為16個小三角形(圖3.7).易知,每個小三角形也是等邊三角形,邊長為3.圖中畫有斜線的三角形共有10個,作每一個這種三角形的外接圓.經(jīng)容易計算可知,這種圓的半徑等于3.計算表明,這樣的十個圓盤不只是蓋住了畫有斜線的三角形,而且也蓋住了那六個沒有畫斜線的小三角形.也就是說,這十個圓的并集籠罩了本來的等邊三角形ABC.由抽屜原理,ΔABC內(nèi)的隨意21個點中,至少有三個點屬于同一個小圓盤.命題得證.【例12】正方形被九條直線分割,每一條都與正方形的一對對邊相交,把該正方形分成面積之比為2∶3的兩個梯形.求證:這九條直線中必至少有三條相交于同一點.證實如圖3.8所示,設(shè)CD是一條滿意題中條件的直線.我們再畫出這兩個梯形的中位線AB.因為這兩個梯形有相等的高,因此它們的面積之比應(yīng)該等于對應(yīng)的中位線長的比,即等于AP:PB(或者BP:PA).從而點P有決定的位置;它在正方形一對對邊中點的連線上,并且AP:PB=2:3.由幾何上的對稱性,這種點共有四個,即圖3.8中的P,Q,R,S.我們的九條滿意條件的分割直線中每一條必須過P,Q,R,S這四點中的一個.把P,Q,R,S【例13】在平面上隨意給定1980個點,其中隨意兩點的距離均大于2.求證:其中必有220個點,彼此之間的距離都小于2.證實 因為1980÷220=9,因此應(yīng)該異常注重9這個數(shù)字.設(shè)想在該平面上已經(jīng)建立了一個直角坐標系,兩族直線x=整數(shù),y=整數(shù)把囫圇平面分成了無限多個邊長為1的小正方形.我們將在第一象限中最逼近原點的九個小方格編上從1到9的號都編上了1至9中的一個號碼碼(圖3.9),我們把這九個方格平行地往上、往下、往左、往右推移三個小方格,從而就把附近4×9=36個小方格按同樣的方式編了號﹔用同樣的主意來推移這些新編了號的九個小方格,并且無止境地做下去,便把全平面上的每一個小方格都編上了1至9中的一個號碼.因為給定的點之間的距離大于2,可見沒有兩個點會落在同一個小方格中.因此,給定的1980個點便分布在1980個不同的小方格中.這些小方格被分成了九類,即有相同編號的點被視為一類.由原則2,至少有220個點會落在同一類的不同方格中,由編號的主意可知,這些點互相之間的距離?2.證畢.4愛爾迪希-澤克瑞斯定理先講一點容易的知識.按照一定順序羅列起來的數(shù)串a(chǎn)1稱為一個數(shù)列.倘若其中包含無窮多項,則稱之為無窮數(shù)列;若只含有窮項,則稱之為有窮數(shù)列.無窮數(shù)列和有窮數(shù)列統(tǒng)稱為“數(shù)列”.每個ai稱為數(shù)列的項,正整數(shù)i1,2,3,?1,-1,1,-1,1,-1,?1,它們都是數(shù)列,其中前兩個是無窮數(shù)列,最后一個是有窮數(shù)列(因為它只含六項).倘若數(shù)列(1)滿意a則稱它為一個升高數(shù)列;倘若上述不等式中的每一個“≤”都成立著不等號“<”,則稱它為鄭重升高數(shù)列.類似地,倘若數(shù)列(1)滿意a則稱它是一個下降數(shù)列;倘若上述不等式中的每一個“””都成立著不等號“>”,則稱它為鄭重下降數(shù)列.升高數(shù)列和下降數(shù)列統(tǒng)稱為單調(diào)數(shù)列.例如,前面三個數(shù)列中的第一個是單調(diào)數(shù)列,并且是鄭重升高數(shù)列;而后兩個數(shù)列都不是單調(diào)數(shù)列.從數(shù)列(1)中取出一部分項,但不改變它們在原數(shù)列中的先后順序,這樣就得到了一個新的數(shù)列.稱之為數(shù)列(1)的一個子數(shù)列.數(shù)列(1)的任一個子數(shù)列可以這樣來表示:a其中下標必須滿意1?這就是說,子數(shù)列中項的先后順序必須保持它們在原數(shù)列中的先后順序.注重以下兩種極端情況:數(shù)列(1)本身一定是數(shù)列(1)的子數(shù)列;隨意抽出數(shù)列(1)的某一項所組成的數(shù)列必是數(shù)列(1)的子數(shù)列.很顯然,這兩種極端情況徹低符合子數(shù)列的定義.有了上述這些決定之后,就可以繼續(xù)舉行我們的研究了.【例1】隨意給定由n2+1個項所組成的實數(shù)列.求證:從中一定可以挑出由n+1為了詳細地了解這個結(jié)論說的是什么內(nèi)容,在證實之前,我們來看幾個異常的情況.當(dāng)初n=1,n2+1=2,n+1=2.這就是說,隨意給定由兩個項組成的實數(shù)列,從中一定可以取出由兩個項組成的單調(diào)子數(shù)列.這是不證自明的,因為任何兩個實數(shù)所組成的數(shù)列一定是單調(diào)數(shù)列.當(dāng)初n=2,n2+1=5,n+1=3.這就是說,隨意給定由五個項組成的數(shù)列,從中一定可以取出由三個數(shù)組成的單調(diào)子數(shù)列.即使在證實 把原數(shù)列記為a1將以ai作為首項的、項數(shù)最多的下降子數(shù)列的項數(shù)記為Ni.因為單單是一個ai就可組成一個下降子數(shù)列,所以Ni?1.這就是說,N1,N2,?,Nn2+11?的情況.當(dāng)n2+1個天然數(shù)Ni只浮上1,2,?,n這n種可能時,由原則Ni1其中下標滿意1?現(xiàn)在我們來證實:子數(shù)列a是鄭重升高數(shù)列.可以用反證法.假設(shè)a那么,以ai為首項的、具有最大項數(shù)的下降子數(shù)列,起碼要比以ai2為首項的、具有最大項數(shù)的下降子數(shù)列多一個項.也就是說N這與等式(2)矛盾.所以,只能是ai1a這就是說,在原數(shù)列不包含由n+1個項所組成的下降子數(shù)列的情況下,我們證實了原數(shù)列一定含有由n+1個項所組成的鄭重升高子數(shù)列.所需的結(jié)論就徹低證實例1所涉及的問題,還可以深人地研究下去.下面我們推薦例1的一個推廣.【例2】愛爾迪希-澤克瑞斯(Erd?s-Szekeres)定理:隨意給定由l個互不相等的實數(shù)a1,a2,?,al所組成的數(shù)列,其中l(wèi)>mn(m與n均為天然數(shù)).倘若其中每一個下降子數(shù)列至多含n個證實 這里給的是一個容易的證實,載于J.ofLondonMath.Soc.(《倫敦數(shù)學(xué)會雜志》)第34卷(1959年)第352頁.由此可見,這是一個比較近代的結(jié)果.在這個證實中,用到了抽屜原則.對每一項ai,仍用Ni記以ai為首項的、項數(shù)最多的下降子數(shù)列所包含的項數(shù),又用Mi記以aia表示這樣一種對應(yīng)關(guān)系,即數(shù)列中的任一項均對應(yīng)一個由兩個天然數(shù)組成的有序偶.這種有序偶共有l(wèi)個,即與原數(shù)列中的項數(shù)一樣多.假設(shè)1?Ni?n,并且1?Mi?m對i=1,2,?,l都成立,那么這種數(shù)偶的類型至多有nm種.因為l>nm,按照N同時成立.現(xiàn)在我們來證實這一情況根本不可能浮上.不妨設(shè)i<j,依題設(shè),此時,若ai<aj若ai>aj總之,當(dāng)初i≠j,Ni=Nj與Mi=Mj不可能同時成立.由此矛盾可知,倘若1?Ni取l=n2+1,就得倘若l=mn,那么l>n(m-1).設(shè)數(shù)列a1,a2,?,al中最長的下降子數(shù)列的項數(shù)為n,則由本例可知,一定存在一個至少由m項所組成的升高子數(shù)列.普通來說,結(jié)論中的n共含mn項,它所含的最長下降子數(shù)列的項數(shù)為n,所以它含有一個至少由m項所組成的升高子數(shù)列.例如,子數(shù)列n,2n,3n,?,mm就是一個升高的數(shù)列,但是,它的任何含5剩余類先從兩個詳細的例子談起.【例1】在坐標平面上,我們把兩個坐標都是整數(shù)的點稱為整點.對隨意給定的五個整點,求證:其中一定有兩個點,使得其連線的中央仍為整點分析 兩點x1,y1和x2,y2的連線的中點是x1+x22,y1+y22.當(dāng)x1,x2與y1,y2均為整數(shù)時,(奇,奇)，(奇,偶),(偶,奇),(偶,偶).當(dāng)任給五個平面整點時,按照原則1,一定至少有兩個點屬于同一類型.證實 設(shè)在五個整點中,屬于同一類型的兩個整點是x1,y1,x2,y2,即x1,x2以及y1,y2有相同的奇偶性.所以【例2】在空間直角坐標系中,我們把三個坐標都是整數(shù)的點稱為整點.對空間中隨意給定的28個整點,求證:其中一定有兩個點,其連線上的三等分點仍為整點.讀者一定會認為,例2和例1是屬于同一性質(zhì)的問題,因此用大致相同的主意就能加以解決.這種看法是準確的.不過,再想用“奇數(shù)”、偶數(shù)”來說明它,卻是不可能的了.為了簡明地說清晰這一大類問題,我們首先來推薦“同余”和“剩余類”的概念,而把例2的證實放在本節(jié)的最后.首先推薦一個函數(shù)[x].設(shè)x是任一實數(shù),用[x][這個定義意味著以下三點:(a)[x](b)整數(shù)[x]不超過(c）比[x]再大的整數(shù),哪怕是[x]+1,把這三條合在一起,則知:[x]是不超過x的最大的整數(shù).我們稱[x]為x[5]=5,[0.9999]=0,[-3.6]=-4,[-7]=-7.倘若π表示圓周率,那么[函數(shù)[x]現(xiàn)在,設(shè)m是一個正整數(shù),a為任一整數(shù),令q從而,依照定義,有q用正數(shù)m遍乘上述不等式,得到mq再令整數(shù)r于是0?這就是說,m為任一正整數(shù),a為任一整數(shù),則必存在整數(shù)q和r,使得a這里,q稱為m除a所得的不徹低商,而r稱為m除a所得的余數(shù).當(dāng)初r=0,稱m可以整除a,或稱a可被m整除,記為m∣a.例如,15=5×3+0(5∣15,21=5×4+1(-21=5×(-5)+4普通地,用正整數(shù)m去除任一整數(shù)時,余數(shù)不外乎0,1,2,?,這m種情況.設(shè)a,b是兩個整數(shù).倘若用m去除它們,將有整數(shù)q1,q2a并且0?r1<m,0?r2<m.當(dāng)初r1a來表示.例如:15≡0(mod5),14≡9(mod5),18≡-6(mod8),等等.關(guān)于模m同余,還可以用另一種方式來刻畫,即:a≡b(modm)的充足須要條件是m∣(b先證須要性.當(dāng)式(1)和(2)中的r1=rb==因為q2-q1是整數(shù)再證充足性.設(shè)m∣(b-a),則有整數(shù)q,使得b==因為q1+q為整數(shù),故上式表明:用m去除b時余數(shù)也是r1,因此,b和a以一個隨意固定的正整數(shù)m為模,可以把全體整數(shù)按照余數(shù)來分類:凡用m來除有相同余數(shù)的整數(shù)都歸為一類.這樣,便可把全體整數(shù)分成m個類:{0},{1},{2},?,{第一類包含能被m整除的所有整數(shù),第二類包含被m除余1的所有整數(shù),如此等等.這m個類稱為關(guān)于模m的剩余類.再強調(diào)一次:關(guān)于模m的剩余類惟獨m個.在日常生活中,剩余類的概念是見得無數(shù)的:用2作模,可把所有整數(shù)分為兩大類,這就是通常人們所說的雙數(shù)和單數(shù);用7作模,就把無窮盡的日子分成了七大類,即:星期日、星期一……星期六，人們按照這一分類來安頓學(xué)習(xí)、勞作、工作作和歇息.現(xiàn)在我們來給出例2的證實.以3為模,可將全體整數(shù)分為三個剩余類,因此,一切空間整點(x,y,z),可以按照其每一個坐標所屬的剩余類的三種情況,劃分為3×3×3=27類.任給28個空間整點,按照原則1,x或者說,三個數(shù)x都可被3整除.由解析幾何可知,將x1,yx=x=顯然,它們的各個坐標都是整數(shù),因此這兩個點都是整點.為了第9節(jié)中的應(yīng)用,我們在這里把例1的結(jié)論作一推廣.在有序數(shù)組x1,x2,?,xn中,倘若【例3】隨意給定2n+1個n維整點.求證:從中可以選出兩個n維整點x1,x是一個n維整點.證實 宛若例1的證實,我們可以對n維整點的每一個分量(例如,xi叫做n維點x1,x2,?,xn的第i個分量)的奇偶性作分類,或者說,按模2來分類.因為每一個分量有且惟獨兩種可能,因此一共可以分為2n個類.而整點的數(shù)目多于類數(shù),由原則1便知,至少從中可選出兩個整點,記為x1,x2,?,xx也是一個n維整點.證畢.【例4】隨意給定正整數(shù)m.求證:一定有m的某一個整倍數(shù),它徹低由0和1兩個數(shù)字所組成.證實考察正整數(shù)列:1,11,111,1111,?,我們把它們歸人關(guān)于模m的剩余類中.前已指出,關(guān)于模m的剩余類惟獨m個,而上述m+1個數(shù)歸人m個剩余類時,依照原則1,其中一定至少有兩個數(shù),例如說a和b(不妨設(shè)a<b),屬于同一剩余類,即a≡b(modm).這就是說,b-a是m的一個整倍數(shù).另一方面11?100?0這就是我們要證的結(jié)論.【例5】設(shè)a1,a2,?,an是n個隨意給定的整數(shù).求證:其中一定可以找到延續(xù)的若干個數(shù),它們的和可a1,倘若這n個整數(shù)中至少有一個能被n整除,結(jié)論就不證自明了.因此,設(shè)上述數(shù)列中沒有一個是n的整倍數(shù),于是,當(dāng)我們把它們分到關(guān)于模n的剩余類中去時,它們只能進人以下n-1個類{1},{2},?,{可是數(shù)列(3)中有n個整數(shù),按照原則1,數(shù)列(3)中至少有兩個數(shù)a1+?+ak和aa可被n整除.這正是我們所需的結(jié)論.在以上五個例子中,“抽屜”的設(shè)置是比較顯而易見、直截了當(dāng)?shù)?下面的這個例子,乍看起來似乎與抽屜原則不搭界,但經(jīng)過細致的分析和分類,可認識到它確實只涉及抽屜原則.【例6】隨意給定七個整數(shù).求證:其中必有兩個數(shù),其和或其差可被10整除.證實 設(shè)這七個整數(shù)為x1,x2,?,x{0},{1},{2},?,{8},{9}倘若xi≡xj(mod10)(i≠j),那么10∣xi-xj.這樣就得到了所需的結(jié)論,接下來應(yīng)研究(1)倘若惟獨一個數(shù),例如說x7落在這四類之一中,當(dāng)初x7∈{6},-x7∈{4};當(dāng)初x7∈{7},-x7∈{3};當(dāng)初x7∈{8},-x7∈{2};當(dāng)初x7∈{9},-x7∈{1}.我們研究數(shù)x1(2)倘若惟獨x6,x7屬于{6},{7},{8},{9}中的某兩個,(3)倘若恰有x5,x6,x(4)倘若恰有x4,x5,x總之,對這四種情形,都可以用把七個蘋果放人六個抽屜的推理,得到的結(jié)論是:在x1,?,x7中必有兩個數(shù),它們的和是【例7】設(shè)m為任一偶數(shù),有m個正整數(shù),其中每一個均不超過m,并且所有這些數(shù)的和為2m.求證:一定可以把這m個正整數(shù)分為兩組,使得每組中各數(shù)之和均為m證實不妨設(shè)這m個整數(shù)為a1,1?令s另作一個整數(shù)a1-am,考察下列s其中一定有兩個數(shù)關(guān)于模m同余.分以下情況來研究.(1)倘若有下標i,j滿意(1?i<j?m),1?所以只能是sj-si=m,也就是ai+1+?+aj=（2）倘若某一個si與a1-am關(guān)于模m同余,(1)倘若i=1,即m∣am,則因1?am?m,所以am=(2)倘若i=ms從而m∣sm-a1+am相當(dāng)于m∣am-a1(3)設(shè)2?i?s但由1<故只能得出a2+?+ai+am=m.這時將【例8】設(shè)F0=F1=1F這樣定義出的數(shù)列稱為斐波那契數(shù)列.對隨意給定的正整數(shù)m,求證:在斐波那契數(shù)列中,一定可以找到m的整倍數(shù).證實令fn是用m去除Fn所得的余數(shù)(n=0,1,2,?),則整數(shù)對fn,fn+1(n=0,1,2,?)至多惟獨F由此推知F按斐波那契數(shù)列的定義,上式即Fp-1F由最后兩式,知Fq-p+1-Fq【例9】設(shè)素數(shù)p>2.求證:存在整數(shù)x與y,使得p∣1+x2+y2.證實x作x2,我們指嵐這p+12個數(shù)關(guān)于模p互不同余.設(shè)0?x10<因此,p既不能整除x1+x2,也不能整除x2-x1.因為p為素數(shù),故p不能整除x1+x2xy作-1+y2,共有p+12個數(shù),它們關(guān)于模p也是互不同余的.把以上兩組數(shù)x2與-1+y2放在一起,共有p+1個數(shù),因此在這組數(shù)中必有兩個關(guān)于模p同余,x也就是x2+y2+1≡0(modp到此,我們已經(jīng)見到了大量的使用抽屜原則來證實的例子.倘若現(xiàn)在對抽屜原則作一些補充的說明,大家一定會有更深刻的認識和體味.第一,在數(shù)學(xué)中,偶爾需要證實具有某種性質(zhì)的對象的存在,我們常說它們是“存在性證實”.抽屜原則就是存在性證實的一種手段.前面已經(jīng)提到,在任何由366個以上的人組成的人群中,一定至少有兩個人的生日相同.我們無須一個一個人地閱讀他們的出生證件,就可以斷然地指出這一點.但是,抽屜原則不能指明畢竟是哪兩個人有相同的生日,若堅持做到這一點,那就只能去查出生證件了.這是數(shù)學(xué)中證實存在性的特有方式,它對其他的應(yīng)用科學(xué)不能適用.例如,若某個醫(yī)學(xué)家聲稱發(fā)現(xiàn)了一種新的細菌,那么他必須拿出詳細的細菌標本來,雖說不可能讓全世界每一個人看到,但至少也應(yīng)該讓一些有權(quán)威的、為人誠實可靠的同行們看到這些標本.火星上有沒有生命存在?這向來是一個商議不休、沒有結(jié)論的問題.那些堅持說有生命的人,一直拿不出詳細的標本來支持“存在性”;看來是持反駁意見的人占了優(yōu)勢,因為他們指出火星上不具備使生命存在的條件.第二,需要說明的是,倘若一個問題可以用抽屜原則的推理來解決,那么它一定可以利用反證法的推理來解決.這是因為,抽屜原則的準確性是經(jīng)由反證法來確立的.以原則1為例,倘若每個集合所含的元素至多有一個,那么n個集合至多只含n個元素,與元素的總數(shù)多于n個的前提矛盾.我們指出這一點,為的是讓讀者認清這兩者之間的關(guān)系,決不是一定抽屜原則自立存在的意義.反證法是一個很大的概念,反證法的技巧隨著問題的不同有著很大的變化;而抽屜原則可應(yīng)用的對象往往有著比較顯然的特征.因此把這個原則自立地加以強調(diào),是很有須要的.6平均值原則設(shè)a1,a2,?,aa叫做這n個數(shù)的算術(shù)平均值.還可以定義其他形式的平均值,但在本書中只研究算術(shù)平均值,因此直接地稱之為平均值好了.關(guān)于平均值,我們有以下的注記：倘若n個實數(shù)的平均值為a,那么其中至少有一個數(shù)本身不小于a,也至少有一個數(shù)不大于a.這個原則與抽屜原則有密切的關(guān)系,而且它的證實主意與抽屜原則的證法幾乎是一模一樣的,用的是反證法:倘若每一個數(shù)都小于a,那么這n個數(shù)的和會小于na,因此這些數(shù)的算術(shù)平均值將小于a,這是矛盾.同樣地證實結(jié)論的第二部分.為了同抽屜原則作對照,我們天然可以對平均值原則作如下理解:把總量為a1+a2+?+an的液體按隨意決定的方式注人n個能盛液體的容器中,那么至少有一個容器內(nèi)所含液體的量不少于a1+a2+?+ann.固然如此,但因為液體的數(shù)量不一定是正整數(shù),而抽屜原則中的“蘋果【例1】兩個大小不同的同心圓盤各被等分成100個扇形(圖6.1).從每一個圓盤上自立地、隨機地取出50個部分涂上黑色.把小圓盤繞中央舉行旋轉(zhuǎn),轉(zhuǎn)到一個內(nèi)、外的扇形對齊的位置之后,再計算內(nèi)、外色彩相同的扇形的總數(shù).有趣的是:不論原先內(nèi)、外盤的色彩是怎樣涂的,總存在某種位置,使得色彩能匹配的扇形個數(shù)不小于50.證實 轉(zhuǎn)動內(nèi)盤,一共有100種不同的(相對外盤的)位置.注重內(nèi)盤的一個固定的扇形,它在這100次轉(zhuǎn)動中與外盤的扇形發(fā)生色彩匹配的情況恰好有50次.因為這對每一個內(nèi)部扇形都是準確的,所以在這100次轉(zhuǎn)動中色彩匹配的總數(shù)為100×50=5000,可見每一位置的色彩匹配平均數(shù)有50.按照平均值原則可以推知,必存在一個位置,此時的匹配數(shù)不少于50.證畢.與例1緊密相關(guān)的是1989年1月在中國科學(xué)技術(shù)大學(xué)舉行的第4屆全國中學(xué)生數(shù)學(xué)冬令營數(shù)學(xué)比賽的第1題,現(xiàn)講述如下.【例2】在半徑為1的圓周上,隨意給定兩個點集A,B,它們都由有限段互不相交的弧組成,其中B的每一段弧的長度都等于πm(m是正整數(shù)).用Aj表示將集合A沿逆時針方向在圓周上轉(zhuǎn)動jπm所得的集合(j=1,2,3,?).求證l這里,l(X)表示組成點集證實基本的思路與例1的證實是徹低類似的.因為運動的相對性,把B固定只旋轉(zhuǎn)A,也可以看成把A固定只旋轉(zhuǎn)B,后一種看法將給我們帶來方便.先看B上的一段弧,其長度為πm.在我們把B沿順時針方向旋轉(zhuǎn)2m次,每次轉(zhuǎn)角為πm之后,這一段弧與點集A長度的匹配數(shù)顯然是l(A).設(shè)B上有k段這樣的弧,因此在這21因為l(B1因此,在這2m次轉(zhuǎn)動中,至少有一個位置,其長度的匹配數(shù)不小于上述數(shù)值.由運動的相對性可知,一定存在天然數(shù)k(1?l證畢.【例3】有兩個同心圓盤,各分成n個相等的小格,外盤固定,內(nèi)盤可以轉(zhuǎn)動(參看圖6.1).在內(nèi)、外兩盤的小格中,分離寫有實數(shù)a1,a2,?,a求證:一定可以將內(nèi)盤轉(zhuǎn)到一個適當(dāng)?shù)奈恢?使得內(nèi)、外兩盤上的小格對齊,這時兩盤上n個對齊了的小格中的兩數(shù)乘積之和為一正數(shù).(1987年安徽省高中數(shù)學(xué)比賽試題)證實轉(zhuǎn)動內(nèi)盤時,一共有n個可能的位置.設(shè)在第一個位置上,所有n對實數(shù)乘積之和記為s1;當(dāng)轉(zhuǎn)動內(nèi)盤到第二個位置上時,對應(yīng)實數(shù)的乘積之和記為s2??當(dāng)內(nèi)盤相對外盤處于最后一種可能的位置時,對應(yīng)實數(shù)的乘積之和記為sn.因此在一切可能的情形中我們可以換一個觀點來看這一個數(shù).看內(nèi)盤上的一個小格中的數(shù)ai,這里i可以取1,2,?,n中的任何一個值.當(dāng)內(nèi)盤轉(zhuǎn)過n個可能的位置時,由aa這里,i=1,2,?,n.因此a這個數(shù)應(yīng)該等于s1+s可見s1,s2,?,sn的算術(shù)平均值是一個正數(shù).由平均值原則,關(guān)于平均值的應(yīng)用,還有下面這樣一個實際問題.【例4】一個車間有一條生產(chǎn)流水線,由五臺機器組成,惟獨每一臺機器開動時,這條流水線才干工作.總共有八名工人在這條流水線上工作,在每一個工作日之內(nèi),這些工人惟獨五名工人到場.為了保證生產(chǎn),一個最容易的主意是:對這八名工人中的每一個,訓(xùn)練他能開動每一臺機器,這樣就需要對工人舉行8×5=40輪技術(shù)訓(xùn)練.但是,因為技術(shù)培訓(xùn)的費用昂貴,應(yīng)該盡可能減少培訓(xùn)的輪數(shù).有人建議:只對三名工人舉行全能性訓(xùn)練,即讓他們學(xué)會開動所有的機器,而其余五名工人,每人只參加一輪培訓(xùn),讓他們每人能開動一種機器,并且他們開動的機器各不相同.這樣,所需培訓(xùn)的輪數(shù)為3×5+5×1=20,比最初的計劃大為節(jié)約.容易證實,在后一計劃實現(xiàn)之后,不論是哪五名工人上班,這五臺機器總是可以開動的,即流水線總能工作.有人提出這樣的問題:能不能還有更節(jié)約的主意?倘若培訓(xùn)的總輪數(shù)少于20,那么在每一臺機器上可舉行工作的工人平均數(shù)就會鄭重地小于4.這說明,至少有一臺機器,對它而言至多有三名可操作的工人.倘若這三名工人某一天沒有到車間來,那么這臺機器不能開動,囫圇流水線就不能工作.這說明:20輪的技術(shù)培訓(xùn)是必不可少的.用平均值原則還可以解答下面一個幾何問題,在講述這一問題之前,我們要引進須要的定義.所謂多面體,是指一個空間的幾何圖形,它由頂點、棱、面所組成,它的面就是一些平面的多邊形.長方體和四面體都是多面體的例子,而且是凸多面體.所謂凸多面體,是指多面體內(nèi)任何兩點的連線,所有落在這個多面體之內(nèi)的幾何圖形.為了解決我們的問題,必須承認一個公式,這是一個異常重要的公式,它把多面體頂點的數(shù)目、棱的數(shù)目以及面的數(shù)目聯(lián)系在一起.確切地說,設(shè)V表示一個多面體頂點的數(shù)目,E表示它的棱的數(shù)目,F表示它的面的數(shù)目,我們有V-這就是聞名的歐拉(Euler)公式.這里我們不能來證實這個公式,但建議讀者用所認識的多面體來驗證這個公式的準確性.我們有:【例5】若一個給定的凸多面體有6個頂點及12條棱,求證:它的每一個面是一個三角形.證實這時,我們已知V=6,現(xiàn)在我們設(shè)k為每一個面上平均具有的棱的數(shù)目.因為每一條棱由兩個面所共有,所以有等式kF由此解得k很顯然,沒有哪一個面上的棱數(shù)能少于3;由此趕緊推知,也沒有哪一個面上的棱數(shù)能多于3,這是因為若有某一個面上的棱數(shù)多于3,那么平均值k必然比3大,這與上式矛盾.因此每一個面上恰有3條棱.證畢.【例6】平面上有nn≥4個互不相同的點P1,P2,?,Pn,在每兩點之間連起直線段,已知其中長度等于證實設(shè)從點Pi出發(fā)的長度為d的直線共有di條i=1,2,?,n.因為Pid由平均值原則知,必有一個di≥3.這表明從P7用有理數(shù)逼近無理數(shù)通過小學(xué)和中學(xué)里的數(shù)學(xué)學(xué)習(xí),大家對有理數(shù)的運算應(yīng)該是很認識的了.所謂有理數(shù),是指那些能夠?qū)懗蓛蓚€整數(shù)之商的數(shù).也就是說,當(dāng)m,n為整數(shù),且m≠0整數(shù)是有理數(shù)的特例.設(shè)n為任一整數(shù),由等式n=設(shè)nm和nnnn可知有理數(shù)的和、差、積、商還是有理數(shù).換句話說,在全體有理數(shù)范圍內(nèi),舉行加、減、乘、除四則運算,其結(jié)果仍不會越出有理數(shù)的范圍(固然,在作除法的時候,不允許用零作除數(shù)).這個性質(zhì)叫做有理數(shù)系統(tǒng)對四則運算的封閉性.異常地,設(shè)a和b是兩個有理數(shù),則可以推知12a+b也是有理數(shù).倘若a≠b,則把a和b畫在數(shù)軸上,它們就是不同的兩個點,1詳細來說,線段0,1的兩個端點是有理數(shù),它的中點12是一個有理數(shù);接著再看兩條線段0,12和12,1,它們各自的中點14和34都是有理數(shù);考察四條更短的線段:0是線段0,1上等距離分布的一組有理數(shù),它們相鄰的兩個數(shù)之間的距離是12n.只要把正整數(shù)n取得充足地大,就能使這個距離變得隨意小.由此可以推知,在線段0,1之內(nèi)的隨意設(shè)m為任一給定的整數(shù),于是將0,1中的任何有理數(shù)7用有理數(shù)逼近無理數(shù)r平移m個單位之后,得到r+m,它就成了線段m,m+1上的一個有理數(shù).這就表明:線段m,m+1上有理數(shù)分布的“密度”決不會低于線段有理數(shù)的稠密性,可以通俗地說成,有理數(shù)在數(shù)軸上是“無處不在”的.盡管如此,囫圇數(shù)軸并不能被有理數(shù)“一家”獨占,也就是說,數(shù)軸上還有許許多多的不能由有理數(shù)來表示的點.中學(xué)的數(shù)學(xué)教科書中給出過最容易的例子:邊長為1的正方形的對角線的長度(用2來記)就不是有理數(shù).在這里,我們可以證實更普通的結(jié)果,即:定理1倘若一個正整數(shù)不是任何整數(shù)的平方,那么這個天然數(shù)的平方根不是有理數(shù).證實設(shè)天然數(shù)k不是任何一個整數(shù)的平方.倘若k是一個有理數(shù),則可設(shè)k=nm,這里m,n為正整數(shù).依題設(shè),k不是整數(shù),即nm不是整數(shù),所以它一定夾在兩個相鄰的天然數(shù)之間,即存在正整數(shù)q,使得q<nmn若令m'=n-qm,n'=km-qn,由前邊那個不等式知,m'是一個正整數(shù)(從而n'也是一個正整數(shù)),并且m'比mm因為m是一個固定的正整數(shù),這根本是不可能的.這個矛盾來自于我們假設(shè)了k為一有理數(shù).這樣我們就用反證法證得了所需的結(jié)論.在上述證實中,我們所利用的主意是一種典型的手段,數(shù)學(xué)上稱為無窮遞降法.它是初等數(shù)論中常用的,而且近年來也浮上在數(shù)學(xué)比賽題目的解答中.這樣一來,我們已經(jīng)證實了一大批非有理數(shù)的存在性.數(shù)軸上的非有理數(shù),稱為無理數(shù)前已證實2為無理數(shù).于是,對任何有理數(shù)r,數(shù)r+2一定是無理數(shù).這是因為,若r+2是有理數(shù),按照有理數(shù)系統(tǒng)對減法的封閉性,將得出2=r+(a)數(shù)軸上全體無理數(shù)的“數(shù)目”,絕不少于全體有理數(shù)的“數(shù)目”;(b)數(shù)軸上無理數(shù)的密集程度,絕不次于有理數(shù)的密集程度.異常地,數(shù)軸上無理數(shù)的全體也是到處稠密的.現(xiàn)在,我們來證實一個刻畫有理數(shù)特性的定理.定理2任何一個有理數(shù),一定能表示成十進有窮小數(shù)或十進無窮循環(huán)小數(shù);反之,任一有窮小數(shù)或無窮循環(huán)小數(shù),一定是有理數(shù).證實顯然,我們只需研究正有理數(shù)的情形就可以了.(a)對隨意給出的一個正有理數(shù)nm(m,n均為正整數(shù)),在用m去除n的過程中,倘若經(jīng)過有窮次計算正巧倘若任何有窮次計算仍不能除盡,那么,在商過nm之后,每除一次的余數(shù)無非是:1,2,3,?,m-1這些有限種可能的情況.由原則(b)十進有窮小數(shù)顯然是有理數(shù).因此只需證實:十進無窮循環(huán)小數(shù)也是一個有理數(shù).事實上,a===這顯然是一個有理數(shù).證畢.由定理2可以推知無理數(shù)的一個特征:無理數(shù)就是那些能且只能表示為十進無窮不循環(huán)小數(shù)的數(shù).有理數(shù)的全體和無理數(shù)的全體組成實數(shù)系統(tǒng).實數(shù)系統(tǒng)可以和囫圇數(shù)軸上的點之間建立一一對應(yīng).【例1】設(shè)有一無窮小數(shù)A=0.a1a2a3?,其中ai(i=1,2,3,?)是0,1,?,證實按本節(jié)的定理2,只需證實A是循環(huán)小數(shù).由A的構(gòu)成邏輯可知,從它的小數(shù)點后第3位開始,每一位數(shù)字只是由它的左邊那兩位數(shù)字決定的.因此,倘若有兩個數(shù)字a,b,使得ab這個兩位數(shù)重復(fù)地浮上一次,例如A=0.?ab?ab?,那么AA今考察有序的非負整數(shù)偶a,b,其中a為奇數(shù),即a=1,3,5,7,9這五種可能之一,b為偶數(shù),即b=0,2,4,最后,建立一個關(guān)于用有理數(shù)逼近無理數(shù)的定理.用有理數(shù)逼近無理數(shù)的可能性,可以很容易由有理數(shù)在數(shù)軸上的稠密性推出.任給一個無理數(shù)α和一個不論多么小的正數(shù)ε,以α為中央,在數(shù)軸上畫出線段α-ε,α+ε.從有理數(shù)的稠密性斷言,在這個小線段里有無窮多個有理數(shù),它們中間的任何一個同下面的定理3及其證實過程提供了詳細找出這些有理數(shù)的途徑.它的更深一層的意思,在證實完畢之后再來細說.我們先來證實一個引理.引理設(shè)x0,x0的n+1個實數(shù),則其中必有兩個數(shù)xk和x證實把區(qū)間[0,1)0它們兩兩無公共點.[0,1)內(nèi)的n+1個點x定理3設(shè)α為任一無理數(shù),n為隨意給定的正整數(shù),則存在一對整數(shù)a,α并且,其中的a還滿意條件:0<證實令mim或者0把iα-mi當(dāng)成引理中的xi,于是,存在下標k和llα即l設(shè)a=l-aα用正數(shù)a去除上式的兩邊,就證得了α因為a≥1,故有α-ba<1n,我們可以把n取得充足大,以使1n充足8面積的重疊原則抽屜原則又稱為重疊原則.實際上,第2節(jié)中所講述的原則1、原則2和原則3都是最容易的重疊原則.現(xiàn)在,要講述另外一種重疊原則,這就是關(guān)于面積的重疊原則.假定平面上有n個區(qū)域(所謂區(qū)域，是指由一條平面封閉曲線所圍成的內(nèi)部,例如,一個圓或長方形的內(nèi)部都可以叫做區(qū)域),它們的面積分離是A1,A2,?,An.倘若我們把這n個區(qū)域按任何一種方式一一搬到某一個面積為A這個原則同樣是很顯然的,也可用反證法加以證實:假設(shè)它們搬到固定區(qū)域的內(nèi)部而可以沒有公共點,那么,它們的面積的和A1+A天然,對體積也有類似的重疊原則.現(xiàn)在,運用關(guān)于面積的重疊原則,來證實一個重要而有趣的定理.定理1以原點O為對稱中央,隨意畫一個長方形ABCD(圖8.1).倘若此長方形的面積大于4,那么,在它里面除了O點外,一定還有其他整點.證實以那些坐標為偶數(shù)的整點2k,2l為中央,作出一系列邊長為2的正方形.長方形ABCD必然被某些2×2的正方形所蓋住.把這些正方形一個一個地前下來,并把它們平行地移到和中央在O的那個2×2的正方形A'注正方形A'B'C'D'的面積等于4,而長方形ABCD的面積是大于4的.按照面積的重疊原則,至少有兩個碎片會有公共點.設(shè)一個公共點的坐標是(s,t),其中-1≤s考察點Q關(guān)于原點O的對稱點Q'.因為已知長方形ABCD關(guān)于原點對稱,得知Q'必然也在此長方形內(nèi).由對稱性可知,Q'的坐標是-2m'-s,-2n'-t.既然P和Q'2m和2n這表明R是包含在長方形ABCD中的一個整點,并且,R和原點O顯然是不同的,這是因為,若R=0,則得m=m'定理1是數(shù)論的一個分支“數(shù)的幾何”中的一個基本定理的一個特例.倘若讀者希翼學(xué)習(xí)這一基本定理,可參閱《格點和面積》一書(閔嗣鶴著,人民教誨出版社,1964年版).利用定理1,我們來解決一個異常有趣的幾何問題.【例1】設(shè)有一座圓形的公園,中央為O點,半徑等于50米.以O(shè)點為坐標原點,選取過O點的互相垂直的兩條直線為坐標軸,建立平面直角坐標系,并選取單位長度為1米.倘若在圓內(nèi)除點O以外的每個整點處都種上一棵小樹,那么,當(dāng)這些小樹長得充足粗的時候,從公園的中央O環(huán)顧四面,視線都會被樹干所遮斷,使人看不到公園的邊緣.現(xiàn)在問:當(dāng)樹干長到多粗時,才會發(fā)生所說的這種情況?我們的答案是:當(dāng)樹干的半徑大于150米(即2厘米)時,從點O朝任何方向看去,視線都會被遮斷;而當(dāng)樹干的半徑小于1證實先證答案的第一部分.我們用ρ表示樹干的半徑,并設(shè)ρ>150在圓O中,任取向來徑AB(圖8.3).過A和B兩點分離作圓O的切線,并作兩直線FG和EH平行于AB,且與AB的距離均為ρ,這樣就得到了一個長方形EFGH.顯然,長方形EFGH的面積100×2ρ>100×2×150=4因此,按照定理1,在這個長方形內(nèi)有一個整點Rm因為m2m即是說,R還在公園內(nèi).R的關(guān)于O的對稱點R'因為R和R'都是公園內(nèi)的整點,且這兩點都不與O重合,因此,這些點上是種了樹的.很顯然,以R和R'為中央、以ρ為半徑作出的兩個小圓一定和直徑AB在O的兩邊相交.這就是說,當(dāng)初ρ>150,OA和OB兩個方向的視線都會被樹干遮斷.因為直徑AB是現(xiàn)在證實答案的第二部分.在坐標為50,0的P點處作圓O的切線,在這切線上取坐標為50,1的整點Q(圖8.4).很顯然,在線段OQ上不再會有整點了.在圓內(nèi)的整點中,離直線OQ最近的整點是R49,1,作RS⊥OQ故有RQ因此RS從而知,當(dāng)初ρ<12501,R那一點上的樹干不會遮斷OQ方向的視線,其余整點上種的樹就更不可能干擾視線OQ顯然,倘若n個區(qū)域的面積之和小于固定區(qū)域的面積,即A那么,把這n個區(qū)域隨意搬到固定區(qū)域內(nèi)部之后,固定區(qū)域一定不能被這n個區(qū)域徹低蓋住,即固定區(qū)域中至少有一個點不屬于這n個區(qū)域中的任何一個區(qū)域.用這樣一個極其顯然的道理,也可以去解一些有趣的題目.【例2】在一個20×25的長方形中,隨意放進120個1×證實我們用反證法來證實.假設(shè)按某一種方式放進120個1×從長方形ABCD(圖8.5)的每一邊剪去一個寬為12的長條,余下一個19×24的長方形A'倘若P為A'B'C'D'內(nèi)的任一點,以P點為中央、以12為半徑作一個圓,它一定會所有在長方形ABCD之內(nèi),依假定,它一定會和某一個1×在EFGH的四條邊上各安裝一個12×1的長:EE21因為P到EFGH的距離不超過12,故P必落入這一圖形中.因為點P是在A'B'C'D'中隨意選取的,我們便可得到這樣的結(jié)論:長方形120但是120×這個矛盾表明,在長方形ABCD中隨意放進120個1×1的正方形之后,一定還有一塊空地可以放進一個直徑為1的9國際數(shù)學(xué)奧林匹克中的幾個賽題現(xiàn)在,在世界上各個國家和地區(qū),每年都在舉行著不同層次的數(shù)學(xué)比賽,其中被公認水平最高的是國際數(shù)學(xué)奧林匹克(InternationalMathematicalOlympiad,簡記為IMO),第1屆IMO是1959年舉行的,1990年第31屆IMO在我國北京舉行,參加的國家和地區(qū)已逾50個.在歷屆IMO的試題中,與抽屜原則有關(guān)的試題以很高的頻率浮上,下面就向讀者推薦這些題目及其解法.【例1】隨意地給定一個△ABC及其一個內(nèi)點P.直線AP,BP,CPAP中,至少有一個不大于2,也至少有一個不小于2.(第3屆IMO試題第4題)證實由圖9.1可見下列三個等式的準確性:PPP因為△PBC的面積+△APC的面積+△ABPP這表明上式左邊三個量的算術(shù)平均值為13.按照平均值原理,這三個量中至少有一個不大于13,也至少有一個不小于13【例2】設(shè)有17位科學(xué)家,其中每一個人都和其余所有的人通信,在他們的通信中,只研究三個題目,而且每兩個科學(xué)家之間只研究一個題目.求證:至少有3位科學(xué)家互相之間在研究同一個題目.(第6屆IMO試題第4題)證實從這17位科學(xué)家中,隨意找出一位,不妨稱之為X先生,X先生同其余16位科學(xué)家通信,研究的是三個題目.因為16=3×5+1,由第二種類型的抽屜原則可知,至少有6位科學(xué)家在同X先生研究著同一題目,不妨稱此題目為題目1.倘若這6位科學(xué)家中,有2位也在題目2與題目3.從這6位科學(xué)家中,請出一位Y先生,他同其余5位科學(xué)家通信,只研究兩個題目.因為5=2×2+1,再一次運用抽屜原則,得知Y先生一定同至少3位科學(xué)家之間研究同一題目,例如說是題目2.倘若那3位科學(xué)家中有兩個人也在研究題目2,命題又已得證.排除這一情況后,那3位科學(xué)家只能是互相研究題目3,這樣,命題也已得證.證畢.注本題中,我們使用了兩次抽屜原則,每用一次,就把范圍縮小一點,然后注重到各種可能的情況.以后的題目中,有的需要更多次地使用抽屜原則.在第二步中,我們證實的結(jié)論可以單獨組成一個題目,而且可以改變它的講述方式,例如說:“全世界的人口中,隨意選出六個人來,其中一定有三個人,他們彼此認識或者彼此不認識."請與本書第3節(jié)的例2相對照.【例3】一個凸多面體P1有A1,A2,?,A9九個頂點,多面體Pi是從P1通過平行移動將頂點A1移到Ai而得到的多面體(i=1,2,?,9).求證:在多面體P證實這是一個涉及體積重疊原則的題目.取A1為坐標系的原點,即令A(yù)1=0.仍用Ai(i=1,2,?,9)來記點Ai關(guān)于原點的位置向量.把A1作為位似中央,將凸多面體P1放大,相似比為1:2.這樣便得出另一個多面體,P按照Pi的定義,它的頂點為Ai+AjA所以這些頂點是P的某些頂點的連線的中點.又因為P是凸的,所以這些頂點全在P內(nèi).這說明了,多面體P1,P2,?,P9都被包含在大凸多面體P之內(nèi).因為這九個多面體的體積等于9×P1的體積,比P的體積大,按照體積重疊原則【例4】已給一個集合,由隨意10個互不相等的兩位十進制正整數(shù)組成.求證:此集合必有兩個無公共元素的子集,它們所含的各數(shù)之和是相等的.(第14屆IMO試題第1題)證實一個有10個元素的集合,它共有多少個可能的子集呢?因為在組成一個子集的時候,每一個元素可以被取過來或者不被取過來,因此我們有210=1024種不同的構(gòu)造子集的主意.也就是說,一共有1024個不同的子集，包括空集和全集.對我們的題目,空集與全集絕對不是可以考慮的對象,再看各個真子擴散一切數(shù)字之和.用S來記這個和數(shù),很顯然10?這表明S至多有855-9=846種不同的形式.因為真子集的個數(shù)是1022,所以一定存在兩個子集A與B,使得A中各元素之和=B中各元素之和但是,A與B可能有公共的元素,但這并不要緊.我們剔除A與B中的一切公共的元素,得出兩個不相交的子集A1與B1A因此A1與B1是符合題目要求的子集.【例5】設(shè)a1,a2a求證:在這個數(shù)列中,有無窮多個ama這里,p,q(p≠q)是兩個正整數(shù),而x,y是兩個適當(dāng)?shù)恼麛?shù)證實以a1為模的剩余類有a1個,即{0},{1},?,a1-1.考慮無窮數(shù)列a2,a3,?,則由原則3,其中有無窮多項屬于同一類,不妨設(shè)這一剩余類是a這里,u是某個正整數(shù).其他的屬于此類的任一項ama因為am>aq,故va=(令x=v-u,這是一個正整數(shù).a由此可見,p=1<q.【例6】已知p個方程、q=2pa其中,所有的系數(shù)aij只取-1,0,1三個數(shù)值之一.求證:方程組(1)有一個解x1,(a)x1,(b)其中至少有一個數(shù)不等于零;(c)xj?q(j=1,2,?,q).(證實考察滿意條件yj?p(j-這2p+1個數(shù)中的一個,而又一共有q個位置,從而一共惟獨(2p+1A因為每個aij只能是-1,0或1,所以每一個Ai也都是整數(shù)A(由此可知,由上述y1,y2,?,yq造出來的數(shù)組A1,(2所以一定有兩組不同的y1,y2,?,yq與y1A伩說明a?x它們都是整數(shù),不全為零,并且滿意a而且,對j=1,2,?,qx這說明我們已經(jīng)找到了一個解x1,x2,?,xq,它【例7】一個國際社團的成員來自六個國家,共有1978人,用1,2,?,1977,1978來編號.試證實:該社團至少有一個成員的編號與他的兩個同胞的編號之和相等,或者是其中一個同胞的編號的2倍.(第20屆IMO試題第6題)證實本題與下列問題徹低相當(dāng):“把1,2,3,?,1978按任一方式分成六組,則其中至少有一組有這樣的性質(zhì):其中有一個數(shù),或是等于同組中其他某兩數(shù)之和,或是等于其中某一數(shù)的2倍”.用反證法來證實我們所需的結(jié)論.假設(shè)這六組中的每一組數(shù)都不具備上述性質(zhì),也就是說,每一組數(shù)都具備這樣的性質(zhì)：性質(zhì)*同一組中任何兩數(shù)之差必不在此組中.因為倘若有a,b連同a-b都同在一組中,那么由a因為1978÷6大于329,由抽屜原則,可以絕對有一個組,不妨記之為A,在A中至少有330個正整數(shù).從A中隨意取出330個數(shù)來,其中最大者記為a1.把a1減去其余329個數(shù),它們互不相等并且仍不超過1978.由性質(zhì)*,它們不會再在A組中,而會屬于其余五組.又因329÷5>65,還是按照抽屜原則,可以絕對有一組B,其中至少含上述329個數(shù)中的66個,從B中任取上述66個數(shù)中的最大者,記為b1.再把b1減去其余65個數(shù),得出的差顯然不再屬于B.我們說,它們也不會屬于A.假設(shè)其中某一個數(shù)b1-b屬于A,b其中,a與a'都屬于A,b這就同A具備性質(zhì)*的假設(shè)相違抗.這就說明了,上述的65個數(shù)必屬于其余四組.因為65÷4>16,所以至少有一組,稱為C,包含上述整數(shù)中的17個.反復(fù)舉行上述推理,最后可得一組F,至少含有兩個數(shù),大數(shù)與小數(shù)之差是一個小于1978的天然數(shù),可是它不在A,B,C,D,E【例8】設(shè)一棱柱以五邊形A1A2A3A4A5與B1B2B3B4B5分離為上底和下底.這兩個多邊形的每一條邊以及線段AiBj(i,j=1,2,?,5)證實首先證實上底的五條邊同色.不然的話,一定可以找到相鄰的兩條邊,例如A5A1及A自A1往下底的頂點一共可以引五條線段,即A1Bj(j=1,2,?,5),它們被兩種色彩所涂,因此其中必有三條是同色的,不妨設(shè)它們涂著綠色.這三條綠色的線段中,必有兩條,它們的下端點的標號是相鄰的,例如B1與B2,這就是說A1B1與A1B2是綠色的.依題設(shè),此時B1B2必為紅色.考察△A1A2B2,可知A2B2必為紅色;再看△A2B1B2,這時A2B1為綠色,從而△A1A2B1的三條邊全為綠色,與假設(shè)相違.這就證完了上底的五條邊同色.同理,下底的五條邊也同色.倘若注本題中上、下底的邊數(shù)可以改為2n+1,這里正整數(shù)n?2,證實徹低相同.但邊數(shù)不可改為2n,這時我們可將上、下底的邊隨意涂色.對線段Ai涂紅對相鄰的兩個正整數(shù)j,j+1,這時i+j與i+j+1奇偶性不同,所以AiBj與AiBj+1一定不同色.顯然2n與1的奇偶性也不同,【例9】設(shè)△ABC是等邊的,E是三邊上點的全體.對每一個把E分成兩個不相交子集的分劃,問這兩個子擴散是否至少有一個子集包含著一個直角三角形的三個頂點?給出證實.(第24屆IMO試題第4題圖9.1證實如圖9.1所示,在邊BC,CA,AB上分離取三點P,Q,R,使得PC=BC3,QA=CA3,RB=AB3.很顯然,△ARQ,△BPR,△CQP都是直角三角形,它們的銳角是30°及60°.設(shè)E=E1∪E2,且E1∩E2為空集.由抽屜原則,P,Q,R中至少有兩個點屬于同一子集,不妨設(shè)P,Q∈E1.倘若BC邊上除P之外還有屬于E1的點,那么結(jié)論已明.設(shè)BC上的點除P之外全屬于E2,那么只要AB上有異于B注把點分類和把點“染色”是同一個意思.“分類”的數(shù)學(xué)滋味重一些,染色似乎通俗一些,但本質(zhì)是一樣的.因此,本題可以改述為:對一個等邊三角形邊界上的每一點染上紅色或者綠色中的一種色彩,對任何一種染色主意,你能不能找到同色的三個點,它們組成一個直角三角形?請你給出證實.【例10】設(shè)M是1985個不同的正整數(shù)的集合,其中每一個數(shù)的素因子均小于26.求證:從M中一定可以選出四個不同的數(shù)來,使它們的積等于一個正整數(shù)的四次方.(第26屆IMO試題第4題)證實小于26的素數(shù)共有九個,即2,3,5,7,11,13,17,19,23.我們依次用p1,p2,?,p9來表示它們.a這里,α1,α2,?,α9為非負的整數(shù).這就是說,對每一個a∈M,按式(2)就有一個有序數(shù)組α1,α2,?,α9與之對應(yīng).簡言之,每一個a∈M都唯一地決定一個九維整點.按照第5節(jié)例3的證實中的說法,一切九維整點可以分為29=512類.由M所決定的九維整點共有1985個,所以其中必有兩個,不妨記為α1,ab就是某個正整數(shù)的平方了.仿此舉行反復(fù)推理,可從M中選出[(1985-512)÷2]=736對數(shù):a1與b1,a2與b2,?,a736a等等.這樣,a1b1又決定了一個九維整點γ1,γ2,?,γ9,γ為同類的,即γi+δi=a成立.于是a上式的右邊是一個正整數(shù)的四次方.證畢.【例11】設(shè)x1,x2,?,xn為實數(shù),滿意條件x12+x22a(第28屆IMO試題第3題)證實由柯西不等式,得x即x所以，當(dāng)初0?aia把區(qū)間[0,(k-1)n]等分成kn-1個小區(qū)間,每個小區(qū)間的長度為(k-1)nka共有kn個正數(shù),因此必有兩個數(shù)會落在同一個小區(qū)間之內(nèi),設(shè)它們分離i因此有i很顯然,我們有a現(xiàn)在取a這里,i=1,2,?,n.于是式i這里,ai為整數(shù),滿意ai?10正方形的分解大家知道,圓的直徑就是這個圓的最大弦的長度.現(xiàn)在,我們要把“直徑”這一概念推廣,使得每一個平面上的有界集合都有直徑,不但圓有直徑,而且橢圓、長方形、三角形,甚至有限點集都有直徑,固然,當(dāng)這種推廣了的直徑的概念落實到圓的時候,應(yīng)該與中學(xué)數(shù)學(xué)中圓的直徑的概念一致.定義我們說正實數(shù)d是一個平面上點的集合S的直徑,是指S中的任何兩點之間的距離均不超過d,并且對任何比d小的正數(shù)ξ,那么一定存在S中的兩點,它們之間的距離比ξ大.我們來看以下的例子.倘若集合S僅由兩個不同的點組成,那么這個集合的直徑就等于這兩點之間的距離;倘若S由互不相同的有限個點組成,那么S的距離就等于所有可能的兩點之間距離的最大值;倘若S是一個圓上的點的集合,不管S包不包括圓周上的點,那么S的直徑就是它的半徑的2倍,這與大家熟知的概念是一致的;又如S表示邊長為1的正方形,不管包不包括它的邊界,集合S的直徑都為2;再如S為一橢圓,不管含不含邊界,S的直徑都等于長軸的長度.以上事實的準確性,都可以用上述的定義來檢驗,建議讀者完成這些工作.下面我們研究的點集S,是指一個邊長為1的正方形且包含它的四條邊,即是說S為這個正方形上點的集合.把這個正方形按圖10.1分成三個矩形:CDEG,AFHE,BGHF,其中EG//圖10.1CDEG去掉邊EG之后形成的點集記為S1,矩形AFHE去掉邊FH之后形成的點集記為S2,矩形BGHF上所有點形成的集合記為S3,顯然S1,S2,S1的直徑=S2的直徑==因此,這三個子集的直徑都是658.我們已經(jīng)證實:單位正方形(即邊長為1的正方形)可以分成三個互不相交的子集的并集,并且這三個子集的直徑都等于651958年,在《美國數(shù)學(xué)月刊》第775頁上,加拿大多倫多大學(xué)的李普曼(J.Lipman)證實了下列看上去更有趣的結(jié)論:不可能將單位正方形分解為三個直徑均小于658的、互不相交的點集的并集.他是用反證法來證實的,證實中用到了抽屜原則為了使說理越發(fā)直觀、通俗一點,我們用“涂色”的方式來講述.他的結(jié)論可以等價地表述為:不可能將單位正方形的每點涂上紅、黃、藍三種色彩之一,而使得每一個涂上了相同色彩的點所組成的點集的直徑都小于658用反證法證實.假設(shè)符合要求的涂色方式是存在的,因為S的四個頂點只用三種色彩涂染,由抽屜原則,必有兩點的色彩相同.這同色的兩點顯然不能是位于一條對角線上的兩個頂點,否則涂有這種色彩的點集的直徑為2,大于658.所以同色的兩點只能在S的一條邊上,不失普通性,可設(shè)C與D是紅的.現(xiàn)在來看E,GGD可知這三點一定不是紅點,否則紅點的集合的直徑?658,與假設(shè)不符.所以E,G,F這三點,只能被黃、藍兩種色彩所染FE可知同色的只能是E,G兩點,不妨設(shè)它們是黃點.考慮D關(guān)于E的對稱點K(圖KC可見K與C,G都不同色,故K必為藍點.另一方面BD故B也是藍點.但是KB這表明藍點的集合的直徑必大于658,這與題設(shè)矛盾命題到此徹低得到證實.11不定方程我們暫且不去談不定方程確實切定義,而先從一個詳細的問題談起.“百錢買百雞”是我國古代《張丘建算經(jīng)》中的名題.用現(xiàn)代漢語講述如下:【例1】小雞1元錢三只,母雞3元錢一只,公雞5元錢一只.用100元錢去買100只雞,問小雞、母雞、公雞各買幾只?解用x,y,z分離代表小雞、母雞、公雞的只數(shù),按照x在這里,末知數(shù)的數(shù)目比喻程式的數(shù)目多1.現(xiàn)在,我們是要尋求它們的非負整數(shù)解,而不是普通的解.用3去乘式(2)的兩邊,從所得結(jié)果中減去式(1),得8即4這樣就消去了一個末知量x.由式(3),可以得出7由式(4),可見7∣4(25-y).但是,7為素數(shù),且不能整除4,故有7∣(25-y),即有整數(shù)t,使得25-y我們需要的是非負整數(shù)解,故必須有0?t<257,即t只能取如下四個整數(shù)值txyz075250178184281118384412“百錢買白雞”提供了所謂不定方程的比較容易的例子.不定方程是指末知數(shù)的數(shù)目多于方程的數(shù)目,而且末知數(shù)須受某種限制(如整數(shù)、正整數(shù)或有理數(shù)等)的方程.關(guān)于不定方程,在我國古代有過豐盛的研究,“百錢頭百雞”僅是這種研究成績之一例.【例2】證實:方程x除x=y=z證實若整數(shù)x,y,z滿意方程(5).這時,式(5)的右邊為偶數(shù),從而x2+y2+z2也為偶數(shù).這樣,就趕緊排除了x,y,z三個都是奇數(shù),以及其中是兩偶一奇的情況,這是因為,在這兩種情況下,x2+y2+z2顯然都是奇數(shù).我們說x從而x可是,式(5)的右邊2于是式(5)天然不能成立.這就是說,只需考察x,y,x其中,x1,y1,z1都是整數(shù).x重復(fù)同樣的推理過程,可以說明x1,yx其中,x2,y2,z2均為整數(shù).x這種處理可以無止境地舉行下去.這就表明:整數(shù)x,y,z中都包含著無窮多個因子2.至于x=y=z=0滿意方程在下一節(jié),我們要來研究佩爾(Pell)方程,佩爾方程是一種異常類型的二元二次不定方程,在研究它的過程中,我們反復(fù)地用到了抽屜原則.12佩爾方程嚴士健教授的文章《“抽屜原則”及其他一些應(yīng)用》發(fā)表在《數(shù)學(xué)通報》1957年第7期上,可算是宣傳抽屜原則的最早的文章,文中有關(guān)于“佩爾方程”殘破的段落,我們以之組成本書的最后一節(jié),并向嚴先生表示衣心的謝謝.考慮不定方程x其中,d為正整數(shù).倘若d是某一整數(shù)p的平方,即d=p2,(當(dāng)x,y為方程(1)的整數(shù)解時,x-py和x+x由此推得x即當(dāng)d是一平方數(shù)時,方程(1)惟獨整數(shù)解(1,0)和(-1,0).在d不等于某一天然數(shù)的平方的條件下,方程(1)稱為佩爾方程.讀者天然要問,佩爾方程除了顯然的解1,0和-1,0之外,還有沒有其他整數(shù)解答案是絕對的.本節(jié)通過初等但冗長的計算的推理,證實佩爾方程有無窮多個整數(shù)解,并求出它的所有整數(shù)解的表達式.定理1當(dāng)d不是某一正整數(shù)的平方數(shù)時,有無窮多對整數(shù)xi, x證實首先,因為d是一個非平方的整數(shù),由第5節(jié)的定理1得知,d是一個無理數(shù).依第7節(jié)的定理3,對隨意給定的正整數(shù)n1,有一對整數(shù)x1 x其中,1?y1 x < = ? < = ?1因為d為無理數(shù),x1- x可取適當(dāng)大的正整數(shù)n2,1n2<x對這個n2,又依第7節(jié)的定理3,可求得一對整數(shù)x2x2其中,1?y2?n x由式(3)和(4),知 x繼續(xù)此過程以至無窮,可知存在xi, x其中,yi?1.并且x1由式(5)可見,只要i≠j,就有 x這就是說,滿意條件的整數(shù)對xi,yi定理2存在一個非零的整數(shù)k,使不定方程x2有無窮多個整數(shù)解.證實由定理1得知,有無窮多對整數(shù)xi,y - i=但是,在-2d+1與2d+1 a中,必有無窮項實際上是同一個整數(shù),我們用k來記它.k一定不會等于零,這是因為,假若k=0,將得出d為有理數(shù).正是這個k值,使得方程(6)有無窮多個解.證畢定理3佩爾方程(1)除了顯然解±1,0之外,還有其他整數(shù)解證實倘若x,y是方程(6)的解,顯然x,y也是方程(6)的解.因此,定理2實際上可以說成:存在無窮多對正整數(shù)ξ ξ把整數(shù)對x,y按其各個坐標關(guān)于模k的剩余分類,分成k×k=k2個互不相交的集合.無窮多個正整數(shù)對ξl,ηl被分配在有限個集合之中.依抽屜原則ξi同時成立.這時 k =因為k≠0,ξi下面來證實兩件事:(a)ξiξj-d(b)ξ這兩件事與式(8)合在一起,正巧表明找到了佩爾方程的非顯然解.先來證(a).利用式(7)以及同余式的性質(zhì),便可得到 ξ ≡ ≡ ≡k≡以及 ξ這樣就證完了(a).再來證(b).假設(shè) ξ由此得到 ξ用λ來記這個公共值,于是有 ξ此即k=λ2k.因為k≠0,故λ2=1,從而λ=±1.但因ξi,ξj均為正數(shù),只能是λ=1,由此得ξ注重到式(8),即知我們已經(jīng)獲得了佩爾方程的異于±1,0的整數(shù)解,定理3到此證畢下面求佩爾方程通解的表達式.定理4若x1,y1和x2,yx3所決定的整數(shù)對x3,y3證實事實上,由式(9),可得 x y所以有x3由式(9)和(10),可得 x = = = =這就證得了x3,y3也是佩爾方程(1)倘若x,y是佩爾方程(1)的整數(shù)解,并且x>0,y>0,則稱x,y是方程1的正解.設(shè)x0定理5佩爾方程的所有正解x,y中的x和yx+yd決定.證實因為x0,y0是方程(1)的一個正解,反復(fù)運用定理4,便可知由公式(11)決定的x反過來,設(shè)x,y是方程(1)的任何一個正解.因為x0?1,yx0鄭重升高且趨向于正無窮大.現(xiàn)在,由 x+y可知x+yd一定會夾在數(shù)列(12)中的某兩項之間,即存在一正整數(shù)n, x也就是1?x+y將上式中間那一項改寫為 x+y =并記之為x'+y'd.因為x0,-y0和x,y是方程(1)的整數(shù)解,反復(fù)運用定理4,可以