从鸽笼原理到幸福结局问题

從鴿籠原理到幸福結局問題國立台灣大學數學系張鎮華http://www.math.ntu。edu。tw/~gjchang2003年3月16日摘要。1932年Klein提出這樣的問題：對於給定的正整數n,能否找到一個正整數N（n)，使得平面上任意N(n）點（其中任三點不共線）中，均能找到n點形成凸多邊形。這篇文章主要是在介紹這個被Erdős稱為「幸福結局問題」的來龍去脈，並討論鴿籠原理與拉姆西理論，及他們如何應用在這個問題上。人物出場匈牙利數學奇才PaulErdős於1996年9月24日以八十三歲高齡去世，他一生寫過的學術論文達1475篇，不只數目多，而且分量紮實，其中有許多影響後來的發展甚深。現在要談的是他年輕時和Szekeres合力解決Klein提出來的一個平面幾何問題的一段歷史，以及其後的影響。Erdős於1913年3月26日出生在匈牙利，自小就已顯露其數學才能。1930年代初，Erdős和一些年輕數學家們每週聚會一次，一起聊天、談論時事，尤其是研討數學。週日他們去布達佩斯郊外爬山越嶺，也常在城市公園裡披斗篷的無名者青銅像下的長椅上聚會。在無名者銅像下，Erdős和他的夥伴們有關政治和家庭的話題，總是不如數學多。他們沉迷於數學，其中尤以Erdős最為癡迷，他的熱衷數學，很能帶動同伴們的討論.1932年歲末,在無名者銅像下聚會的人群中多了EstherKlein,她是一個在哥廷根大學唸了一學期,中途跑出來,頗有才華的學生，還有GyorgySzekeres，他是一個急於把試管拋掉而投身數學的化學系畢業生。有一次，在他們每週的活動中，Klein提出一個希奇古怪的平面幾何問題:平面上給定五點，若任意三點不共線,求證必有四點構成凸四邊形。（一個四邊形是由四條只交在端點的邊構成的圖形，正方形、矩形、平行四邊形和梯形都是四邊形;同理可以有五邊形、n邊形等多邊形。至於「凸」是指從多邊形內部任意一點都可以直接「看到」另外一點，也就是，凸多邊形內部任意兩點的連線仍在該多邊形內部；所以正方形是凸四邊形，而成箭頭狀的四邊形不是凸四邊形，因為位於一側箭尾的點不能直接「看到」位於另一側箭尾的點。）Klein證明平面上任意三點都不共線的五點，不外乎下面三種情況，而每種情況下都保證能構成一個凸四邊形，定理從而得證.第一種情況是五點自身就構成一個凸五邊形，其中任意四點均構成凸四邊形。第二種情況是其中一點為其餘四點所包圍，則外部四點構成凸四邊形。第三種情況是其中兩點位於其餘三點所構成的三角形內部。若作一直線通過這兩點,則該直線將三角形分為兩部分,必有兩個頂點位於直線的一端,那麼這兩頂點與原來的兩點構成凸四邊形.幸福結局問題大家都很喜歡Klein這個簡練的證明，於是想要將證明推廣到構成更多邊的凸多邊形。更精確的來說，Klein建議一個這樣的問題：對於給定的正整數n，能否找到一個正整數N(n），使得平面上任意N（n)點（其中任三點不共線）中，均能找到n點形成凸多邊形？這個問題包括兩件事情，首先，這樣的N(n)是否一定存在？其次，如果存在,那麼最小的N（n)是多少？為了方便，我們用N0(n） 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示這個最小正整數.很顯然的N0(3）＝3；而Klein的證明，再加上一個很簡單的例子（三角形的三個頂點及內部一點不構成凸四邊形），就可以得到N0(4)＝5。在他們這一群人中，另一名數學家EndreMakai很快就證明了N0(5)＝9；也就是說，平面上任意三點不共線的任9點中，一定能找出5點構成凸五邊形，而且下面的例子顯示8點是不夠的：由於知到N0（3）＝2＋1，N0(4）＝22＋1,N0（5)＝23＋1，他們動了N0（n）＝2n—2＋1的腦筋。過了一陣子他們就意識到，只靠簡單的論證並無濟於事，於是圈子裡引發出一股急於解決這個問題的激奮情緒。對Szekeres來說，解題的動機主要來自Klein，獲得佳人青睞強烈地激勵他爭取率先提出解法,幾個星期後他就面帶勝利的笑容對Erdős說：『E。P。＊，敞開你那充滿智慧的大腦吧！』Szekeres找出了保證可構成凸n邊形的所需點數，但這個數目比他們猜想的2n-2＋1大很多；___________________________________________________________________________＊E.P。係ErdősPaul的縮寫，和中國人一樣,匈牙利人的姓是寫在前面的。儘管如此，他的證明還是贏得了Klein的芳心，四年後有情人終成眷屬。從此Erdős把這個問題稱為「幸福結局問題」，永垂數學史。Szekeres的證明隱含了拉姆西定理，事實上，拉姆西定理大約在這五年之前提出來，Szekeres可以說是在不知情的狀況下獨立重新發展出拉姆西定理.用後面將介紹的符號表示,他得到N0（n)≤R(n,5;4）。這個上界其實很大，後來Erdős提出一個更好的上界，證到2n—2+1≤N0（n）≤＋1.這一次,上界小了很多，但利用Sterling公式，我們可以得到，Erdős得到的上界和下界2n—2+1還是有一大段距離.他們兩人將上述的結果合寫了一篇文章，1935年發表［1]。遺留至今還有下面這個未解的問題。猜想：N0(n）＝2n—2＋1。不管是拉姆西定理的證明,或者是Erdős的改良上界的證明，都奠基於一個更基礎的道理，叫做鴿籠原理。接下來,我們要來介紹鴿籠原理與拉姆西定理，並且看看他們如何用來證明N0（n）的上界。鴿籠原理登場於數論假定有n＋1隻鴿子和n個鳥籠,如果要讓所有鴿子飛入籠中，則存在某一個籠子裡面至少有兩隻鴿子。這個看起來很簡單的原理俗稱鴿籠原理,也稱抽屜原理，是十九世紀德國數學家Dirichlet提出來，以解決數論上的一些問題，所以也有人將它稱為Dirichlet（抽屜）原理。這個貌不驚人的原理，卻有廣泛而出人意表的許多應用，有很多很深的定理都可以用它來証明。在本文末的附錄裡我們收集了各式各樣深淺不一的題目,它們都能靠鴿籠原理來解決。這裡我們舉幾個例子來說明。首先登場的是數論上的定理(參見［2])。定理1.若x是一個無理數，且n為正整數，則存在某個有理數h/k，其分母k≤n，滿足。【證明】對任一實數y,我們用［y］表示y的整數部分,也就是滿足m≤y＜m+1的唯一整數m。因為x是無理數,對於i＝1,2，…,n恆有0＜ix－［ix］＜1,也就是說,我們有n個在開區間（0，1)的無理數ix－［ix]﹔其實每一個這樣的數也一定在下面這n個子區間之一：（0，1/n）,（1/n,2/n)，…,(（n—1）/n,1)。如果有某一個jx－［jx]在子區間(0,1/n）內，則我們可以取h＝［jx]和k＝j，定理就成立.如果所有這n個無理數ix－［ix]都落在除了（0，1/n）以外的n－1個子區間，則由鴿籠原理，存在某一子區間（r/n,(r+1)/n）包含某兩個數sx－[sx］和tx－[tx］，其中1≤s＜t≤n，這兩個數差的絕對值一定小於1/n,也就是說｜(tx－［tx])－（sx－[sx]）|＜1/n,這時可取h＝［tx］－[sx]和k＝t－s,定理就成立。　　　　　　　　　　　　　　　　　　▄鴿籠原理再一應用例子接下來，再來看一組數論上的題目（參見[3］）。從1到200的整數中挑出101個數，證明存在一數整除另外一個。從1到200的整數中，試找出100個數，使得任一數不整除另一個。從1到200的整數中挑出100個數,如果至少有一數小於16,證明存在一數整除另外一個。首先我們來證明(甲），令選出來的數為xi＝yi，其中ai為非負整數，yi為介於1到200之間的奇數，i＝1,2,…，101。因為介於1到200間的奇數只有100個，根據鴿籠原理，存在i≠j使得yi＝yj，因此，當ai≥aj時xi整除xj,當ai＜aj時xj整除xi。所以(甲)得證。（乙)只是在說明（甲）中的101是不可以再少的.選101，102,…，200這100個數就可以達到目的。最後考慮(丙）,假設選出來的100個數是zi＝wi，其中bi是非負整數，wi為奇數,i＝1,2，…,100。如果不存在某個zi整除另一個zj，則一定有下述性質：(＊）若i≠j且wi整除wj，則bi＞bj。因此，這100個奇數wi必定都相異.假設選出來小於16的數是2bw，則有下列4種可能：b＝3，此時w＝1，所以3bw＝27。b＝2,此時w≤3，所以3bw≤27。b＝1，此時w≤7,所以3bw≤21。b＝0,此時w≤15,所以3bw≤15。在任何情況下，3bw≤27,所以w＜31w＜32w＜…＜3bw＜3b＋1w這b＋2個奇數均小於200,因此它們都對應於各個wi,或者說,存在b＋2個選出來的數形如2bw，31w，32w,…，3bw,3b+1w,由(＊）可知，b＞c1＞c2＞…＞cb＞cb＋1≥0，因此0和b－1之間有b＋1個相異的整數c1，…，cb＋1，矛盾.所以（丙）得證。以上的問題被［4］推廣到更一般的情況.Erdős的巧思在真正證明這個N0（n）的上界之前,Erdős先用鴿籠原理證明了一個類似的定理.定理2。對任一含有nm+1項相異實數的數列x１，x2,…，xnm+1，或者存在一含n+1項的遞增子數列，或者存在一含m+1項的遞減子數列.【證明】對應於每一個xj，令aj表示以xj為末項的遞增子數列最多的項數，bj表示以xj為末項的遞減子數列最多的項數。對於i＜j，當xi＜xj時ai+1≤aj，當xi＞xj時bi+1≤bj，因此序對(ai,bi）≠（aj,bj)。因為有nm個xj，由鴿籠原理可知，不可能所有aj≤n及所有bj≤m，也就是，或者存在一含n+1項的遞增子數列，或者存在一含m+1項的遞減子數列。　　　　　　　　　　　　　　　　　　　　　　▄利用和這個相類似的論證,事實上其中也隱含有証明拉姆西定理的精神,Erdős進一步證明了下面的定理.定理3。當m,n≥2時，平面上給定點，假設任三點不共線，任兩點的橫座標均相異.則或者存在n點x１,x2,…，xn（橫座標由小而大）,其連續線段xixi+1的斜率遞增，或者存在m點其連續線段的斜率遞減。　斜率遞增　　斜率遞減【證明】令f(n，m)表示平面上最多的點數，使得不存在n-杯（n點使得連續線段斜率遞增)，而且不存在m-帽（m點使得連續線段斜率遞減）。我們首先要證明f（n,m）≤f(n，m－1)+f(n－1,m）。　(*)設S是有f（n,m）點但無n-杯無m—帽的點集，令T是所有可為(n－1）-杯右端點的集合，則S\T中沒有(n－1）—杯也沒有m—帽，所以|S\T|≤f(n－1,m）。再者，如果T中有一個（m－1)-帽A,令其左端點為x，左邊倒數第二點為y，由T的定義，x是某一(n－1）-杯B的右端點,令此杯右邊倒數第二點為z；如果zx的斜率小於xy的斜率，則B和y合成n-杯;如果zx的斜率大於xy的斜率，則z和A合成m-帽;兩種情況都不可能，所以T中沒有n-杯及（m－1)—帽，因此｜T｜≤f(n,m－1)，所以(＊)成立。此不等式和巴斯卡等式，再加上數學歸納法可以證明f（n,m)≤，所以定理得證。　　　　　　　　　▄由定理3再加上適當的選取座標軸,使得不會有兩點有相同橫座標，就可以證得N0(n)≤＋1。至於2n-2+1≤N0(n)，則要小心地選取反例就可以得到。雖然Erdős的上界比Szekeres的上界好，但因為後者是採用拉姆西數得到的,這套理論也很值得知道,再者有感於Szekeres是第一個證明N（n)確實有限的人，所以也要來談談他的工作。拉姆西理論及Szkeres的證明鴿籠原理有多種變形,其中之一是：假設有p1+p2+…+pn－n+1隻鴿子和n個鳥籠，如果要讓所有鴿子飛入籠子,則必定存在某個i，使第i個籠子中至少有pi隻鴿子.當p1＝p2＝…＝pn＝2就是最原始的鴿籠原理.拉姆西定理最簡單但還要點證明的情況,可以用下面的例子說明。有6個人，任兩人或者彼此相識，或者彼此不相識（但沒有甲認識乙，而乙不認識甲的情況），證明必存在兩兩互相認識的3人,或兩兩互相不認識的3人。這個事實的證明如下.首先指定一人，在其餘5人當中，他或者與其中3人認識，或者與3人不認識（應用鴿籠原理5＝3+3－2+1）。先考慮他與某3人認識的情況,如果這3人中有某2人互相認識，則這2人與原來選出的那人，合成兩兩互相認識的3人；如果這3人兩兩互相不認識，那定理也得證。選定那人與某3人不認識的情況，其證明亦類似.我們也可以將上述的道理用集合的語言寫出來：假設S是一含有6元素的集合,任意將其所有15個含有2個元素的子集合分成兩類，則S中一定有一恰含3個元素的子集T，這個子集的任何含2個元素的子集都在同一類。這樣的寫法，看起來有點古怪，但有利於後面的一般化。先舉一個例子說明如下:令S＝｛1，2,3，4,5,6｝.第1類2元素子集：{1，2}，{1，6｝，｛2，3},{3，4｝，{4，5}，｛5，6｝。第2類2元素子集：{1,3｝，｛1，4｝，｛1，5}，｛2，4｝，{2,5｝,｛2，6},｛3,5},{3，6}，｛4，6｝.則可以找到T＝｛1,3,5}，其所有2元素子集都是第2類。拉姆西定理。假設正整數p1,p2,…，pn,t滿足p1≥t，p2≥t,…,pn≥t,則一定存在一最小正整數R(p1,p2，…,pn；t)滿足下面性質：假設集合Ｓ至少有R(p1，p2，…,pn；t）個元素，任意將其t元素子集分成n類,則必有某一i（1≤i≤n)使得S有一恰含pi個元素的子集T，其所有t元素子集都是第i類。利用上述定理的符號,則上述6人中3人互相認識，或不認識的事情,就可以寫成R（3,3;2)≤6。事實上，R（3,3;2）＝6，因為5個人就有可能找不到兩兩認識的3人，或兩兩不認識的3人。一般說來，決定拉姆西數是困難的事。t＝1就是一般化的鴿籠原理，也就是R(p1，p2,…，pn；1）＝p1+p2+…+pn－n+1。當t≥2時,就不容易決定R(p1，p2，…，pn;t)了，縱使是R（p，q；2）都不是那麼容易。從定義，倒不難看出R(p，t;t）＝R（t，p；t)＝p,所以上述的R(3,3;2）＝6算是第一個要花一點力氣得到的結果。利用和證明定理3類似的說法，可以證得R(p，q；2)≤R（p－1，q;2）+R（p，q－1;2），再加上巴斯卡等式及數學歸納法，也可以得到R(p,q;2)≤。最後讓我們用拉姆西數的符號來說明Szekeres的上界。定理4。N0(n)≤R（n，5；4）。【證明】假設S是平面上m＝R（n，5;4）點所成的集合，其中任三點都不共線。我們想證明，S中存在n點,構成凸n邊形。首先,將S的所有4元素子集分成二類，第1類是4點成一凸四邊形的子集，第2類是4點不構成凸四邊形的子集。由R(n,5;4)的定義可知：或者存在S的n元素子集T，其任一4元素子集都能構成凸四邊形;或者存在S的5元素子集T,其任一4元素子集都不構成凸四邊形.但是Klein原來的論證已經說明後者不可能,所以前者恆成立,此時，T中的n點必構成一凸n邊形。▄落幕星起星落,1930年的激情匆匆已過七十餘年,當年的一對佳人現在還幸福的住在美國新澤西州,而才子Erdős過世數年。他們留給後人的是一片大好數學江山，以及沉迷數學的回憶。且讓後人續之。欲知後事如何，請看［5,6,7]。參考文獻P。ErdősandG.Szekeres,Acombinatoricalproblemingeometry,CompositioMath.2（1935），463-470。K。Chandrasekharan,IntroductiontoNumberTheory，Springer-　Verlag,NewYork,1968。R。A.Brualdi,IntroductoryCombinatorics，1977.G.J.ChangandF。H。Hao,Theminimumoftheantichaininthefactorposet,Order3（1987）,355-357。F。R。K。ChungandR.L.Graham,Forcedconvexn—goneintheplane,DiscreteComput.Geom。19(1998),367—371.F。ChungandR.Graham,ErdősonGraphs─HisLegacyofUnsolvedProblems,AKPeters,Wellesley,MA，1998。R。L。GrahamandJ。Nesetril，RamseytheoryintheworkofPaulErdős，in:TheMathematicsofPaulErdős（R。L。GrahamandJ.Nesetril,eds)，Springer-Verlag，Heidelberg，1996。PaulHoffman著，米緒軍、章曉燕、繆衛東譯，數字愛人─數學奇才艾狄胥的故事，台灣商務印書館,2001年。BruceSchechter著，曾蕙蘭譯，不只一點瘋狂─天才數學家艾狄胥傳奇，先覺出版社，1999年。附錄（a)400個人之中至少有兩人生日同一天。為什麼？(b）把400換成另外一數而上面的陳述仍然成立,此數最小是多少？(c）要多少人才能保證其中至少有三人生日相同？（d）要多少人才能保證有不同的兩天都有兩個以上的人作生日。有kn＋1個球要放進n個箱子。一定會發生什麼事?沒有人的頭髮超過三十萬根，新竹市的人口是三十萬零一人。你能斷言新竹市有兩人頭上的毛一樣多嗎?箱子裡有70個球五種顏色：20個紅，20個藍，20個黃，其餘的10個球有黑有白。你至少必須拿多少球才能保證拿到10個同色的球？你至少必須拿多少球才能保證拿到全部五種顏色？媽媽俱樂部有28位太太，王太太有I3個小孩，其他人都沒她多.證明至少有三位太太的小孩一樣多。共他條件不變，俱樂部中該有多少媽媽才能保經有四位太太的小孩一樣多？客廳裡有n個人,證明他們之中有兩人在客廳中認識的人一樣多。會場中有n個專家。每個人都和其他人正好握一次手.證明在握手寒喧的這段時間中，每一時刻都至少有兩個人已經握手的數目相同。n個人參加循環賽,每個人都要和別人正好比賽一次。證明在整個賽程中之任一時刻，至少有兩隊到那時刻為止已經賽完了一樣多場。51隻小昆蟲放置在邊長1的方塊內。證明無論何時，至少有三隻昆蟲可以罩在一個半徑的圓內.在平面格子點中選定五個格子點.證明永遠可以找到其中兩點，使得它們的連線通過另一格子點.（格子點是指座標為整數的點。)令P１,P2,…,P9為空間中的九個格子點。證明有一格子點落在某線段PiPk上，i≠k，i,k｛l，2，。..，9}。在一個邊長7的正方體內選定342個點。你能否放置一個邊長1的小正立方體到大立方體內，使此小正立方體的內部不包含選定的這些點?一個靶其形狀為邊長2的等邊三角形。如果射中靶五次。證明有兩個彈孔的距離小於或等於1。如果射中靶17次。關於兩個彈孔之間的最小距離能斷言什麼？在數列1，1，2，3，5,8,3,1，4，5,9,4，3，7，0，7,7，4,1,。.。中每一項都是前兩項之和，只不過加法是在模10下做的。證明此數列是週期的。週期的可能長度最大是多少？證明週期以1，1,2，3,5，…開始。考慮由a1＝a2＝1，an+1＝an—1＋an,n＞1，所定義的費波那奇（Fibonacci）數列,1,1,2,3,5,8,..。。證明對任一n有一費波那奇數尾巴有n個零.假定a與2及5互質。證明對任一n，有一個a的乘冪其尾巴是.有10條線段，每一條都比一寸長,比55寸短。證明可以從中選出三條造出一個三角形。在一間五坪大的房間中放了九塊面積都是一坪的地氈,地氈的形狀沒有限制.證明有兩塊地氈至少重疊了坪。從集合{1，2,...,2n}中任選n＋1個數。證明在這些選出的數中，永遠有一對，大的被小的整除。從集合｛1,2,。.。,2n｝中任選n＋1個數。證明在這些選出的數中，至少有一對是互質的。令n為一自然數，不被2或5整除。證明n有一個倍數全由1組成，即成111…11的形式.S為n個自然數的集合。證明S有一個子集合其元素之和被n整除。證明在六個人之中永遠有三個人彼此都認識，或者有三個人彼此全不認識。空間中給了6點，沒有三點在同一直線上,每兩點都用直線段連結起來,每一線段塗成黑色或白色。證明由這些線段所構成的三角形中，永遠至少有一個，它的邊都同色。空間中給了17點,沒有三點在同一直線上,每兩點都用直線段連結起來，每條線段塗上黑色、白色或紅色。證明有一個三角形它的邊都同色。空間中給了66點，沒有三點在同一直線上，每兩點都用直線段連結起來，線段塗上黑色、白色、紅色或綠色。證明有一個三角形它的邊都同色.推廣24、25、26這一系列的問題。S是一個25個點的集合,其中任一個3個點的子集合中至少有兩點距離小於1.證明S有一個13個點的子集合可以用半徑1的圓盤覆蓋住。證明在a2＋1個東西中，或者有a＋1個同一類，或者有a＋1個不同類。（a）平面上的點分成兩個子集合。證明有兩點距離為1且屬於分後的同一子集合中。（b）平面上的點分成三個子集合。證明有兩點距離為1且屬於分後的同一子集合中。將平面分成七個子集合，使得沒有兩點距離為1且屬於同一子集合.註:至於分成4、5或6個子集合的情況，沒人知道是否永遠有一子集合包含兩點距離為1.錫金尼亞國的公路系統是這樣的：在每個交叉路口有三條公路交會.下圖顯示了這樣一個公路系統的簡單例子。證明錫金尼亞公路系統的下列性質：從任一交叉路口A1出發延著三條路中任一條到下一路口A2向右轉開到下一路口A３。在A3向左轉，這樣繼續下去，一次右轉一次左轉。那麼你最後會回到出發點A1。（a)證明任一含有n2＋1項的實數列，必有一長度n＋1的漸增或漸減子數列。（b）證明任一至少ab＋1項的實數列，必含一個a＋1個項的漸增子數列或一個b＋1項的漸減子數列。(a)證明：存在不全為零且絕對值小於一百萬的整數a、b、c使。(b)若a、b、c是不全為零且絕對值小於一百萬的整數,求證：。（美國，41屆，A4）求證：對任何正數ε＞0，存在正整數n使。(蘇聯，1977）在邊長為1的正方形S內任意取定五點P1,P2,P3,P4，P5，用dij表示點Pi和Pj的距離（1≤i≤j≤5）.求證:至少有一個dij小於。用更小的數代替,命題還成立嗎？(美國，14屆，A2）把邊長為1的正方形分成兩塊，証明：至少有一塊的直徑不小於，而且是具有這種性質的最大數。（這兒,平面圖形的直徑指的是它上面任意兩點的距離的最大值。比如，邊長為1的正三角形的直徑是1，等等。）（美國，19屆，B3）GDCABF求證：在歐幾里得平面上，不可能存在七條不同的直線，使得至少存在六點,每點恰為三條直線的交點；至少存在四點，每點恰為兩條直線的交點.(美國，34屆，A6)求證：在任意的有限二項展延式中，奇次項系數之和等於2的冪.（美國，16屆,A7)A１，A2，…，A1006是有限集X的子集，，（i＝1，2，…,1066）。求證：X中存在10個元素x１，x2,…，x10，使得每個Ai至少含x１，x2，…,x10中的一個元素。（｜S｜表示集合S的元素個數.）（美國,41屆，B4)一個正整數集合中，如果不存在兩兩互質的三個數，則稱它是“協力集"。從1到16的整數集,“協力集"最多可含多少個數?（美國,35屆,A1）從1，4，7，…,97，100中選出20個數組成集合A，則A中必有不同的兩組數，其和都等於104。(美國，39屆,A1)給定mn＋1個正整數a１,a2，…，amn+1，0＜a１＜a2＜…＜amn+1。証明，或者可以找到m＋1個數，使它們中沒有一個數能夠被另一個數整除；或者可以找到n＋1個數，使得依大小排成序列，除最前面的一個數外，每個數都能被它前面的數整除。（美國，27屆，B4）空間中的六點，任三點不共線,成對地連接它們得十五條線段,用紅色或藍色染這些線段（一條線段只染一種顏色），求證：無論如何染色，恆存在同色的三角形。（美國，13屆，A2）在一個舞會上，設沒有一個男孩同所有的女孩都跳過舞,但是，每個女孩至少同一個男孩跳過舞。求證：至少存在兩對舞伴:g、b和g’、b’（b、b’是男孩,g、g’是女孩），使得b沒有同g’跳過舞，而g和b'也沒有跳過舞。（美國,26屆，A4）在三維歐幾里得空間中,任意給定九個格點（座標都是整數的點），則其中必有兩點，使得連接這兩點的線段內部含有格點.（美國,32屆,A1）任意給定n＋1個不超過2n的正整數，則至少有一個數是另一個數的倍數。（美國，19屆，B2)求證:比（＋1)2n大的最小整數能被2n+1整除。（美國，6屆，B5)在任意的十個連續整數中,至少有一個與其餘九個數都互質.（美國，27屆，B2）大廳中聚會了100個客人，他們中每個人都與其餘99人中的至少66人相識.證明：能夠出現這種情況：這些客人中,任何4人裡一定有兩人互不相識。（我們假定，所有的熟人都是彼此相識的，亦即如果A認識B，那麼B也認識A.）大廳中聚會了100個客人，他們中每個都與其餘客人中至少67人相識.證明:在這些客人中一定可以找到4個客人，他們中任何2人都彼此相識。(和問題49一樣，我們假定，如果A認識B，那麼B認識A。）所予4n個正整數使得此4n個整數中任取四個皆形成一比例。證明此4n個整數中至少有n個為相同。任予四自然數A，B，C，D，依次取AB,BC，CD,DA之差（取正值）記作A1，B1,C1，D1，再由A1B1,B1C1,C1D1，D1A1之差（取正值)記作A2，B2,C2,D2,如此繼續，証明:取到最後必定可得四個零。例如:若所予四數為32，1,110,7則可得下結果32，1，110，7，31,109,103，25,78，6，78，6，72,72,72，72，0,0,0,0。(a）試將1到100這一百個數重新排列，使得找不到一組11個數（無論相鄰或相隔）以升或降的次序排列.（b)證明1到101這一百零一個數,無論如何排列，皆可找到一組11個數（無論相鄰或相隔皆可）以升或降的次序排列。（a）1到200這二百個數中，任意找出101個數，證明此101個數中必定存在二數，使得一數可被另一數整除。（b）1到200這二百個數中，選出100個數，使得其中沒有一個數可被其餘任何數整除.　　（c)1到200這二百個數中，選出100個數,若其中有一個數小於16,證明100個數中,必有一數可被另一數整除。(a）證明任予52個正整數，必存在二個數，其差或和可被100整除。　　(b)證明任予100個皆不可被100整除的正整數,一定可找到2個或2個以上的數之和可被100整除。一棋士準備以十一週的時間安排比賽，每天至少比賽一場，但為了免於過分疲勞，規定每週不得超過十二場比賽，證明必有連續若干天中，此棋士恰比賽了二十場。設n為一任意自然數.證明存在一個n的倍數，而此倍數僅含有0與1.再者，如果n與10互質（即不能被2、5整除），則存在某一n的倍數完全是由1組成（如果n不是與10互質，那麼當然不會有數目以11…1的形式而能被n整除）。已知數列0,1,1，2，3，5，8,13,21，34，55，89,…從第三數起每一數為前面二數之和（此數列叫做Fibonacci數列)。請問，在這數列的前100，000，002項中,是否存在一個末四位皆為零的數？是否存在一自然數n，使得（2＋)n的小數部分，即（2＋)n－[（2＋）n］大於0。999999？(a)求證任何自然數n，整數[(2＋）n］為奇數。（b）找出能整除整數［(1＋）n］之2的最高乘冪。證明若p為一奇質數,則p能整除[(2＋）p］－2p+1。十七個人互相通信，每一個人和其他人都互相寫信，在他們信上的討論有三種不同的話題，每一對筆友只寫一種話題。證明至少有三個人他們筆談的是同一話題。證明從十個相異的二位數(十進位制）中,可以選出兩個不相交的子集合，使得其元素之數值和相等.考慮p個方程式,q＝2p個未知數x１，x2,…,xq：a11x1＋a12x2＋…＋a1qxq＝0,a21x1＋a22x2＋…＋a2qxq＝0，…………………………….ap1x1＋ap2x2＋…＋apqxq＝0,係數aij｛–1，0，1}。證明此組方程式有一解（x１，x2，…,xq）使得(a）所有xj(j＝1,2，…，q）為整數。（b）至少有一個j使xj≠0。（c)｜xj|≤q（j＝1，2,…，q)。某一國際組織的1978名會員來自六個成員國,會員分別編號為1，2,…，1978.證明至少有一會員的標號，恰為他同國家另兩位會員編號的和,或為同國家另一位會員編號的兩倍。在平面上給了兩點O、A.對平面上每一異於O的點Ｘ，我們以α（X）表示介於OA及OX的角度的弧度數，從OA反時間方向度量。（0≤α(X）≤2π）.令C(X)為以O為圓心，以長度OX＋為半徑的圓。平面上的每一點都塗上了有限多種顏色中的一種。證明：存在一點Y使得α（Y）＞0，而且其顏色出現在圓C(Y)的圓周上.給了一個集合M包含1985個相異正整數,沒有一個的質因數超過26。證明M中至少包含一組4個相異元素其積為某整數的四次方。假設實數x１,x2，…，xn滿足＝1。求證：對任意整數k≥2,存在n個不全為零的整數ai，｜ai｜≤k－1,i＝1，2，…,n，使得｜a1x1＋a2x2＋…＋anxn｜≤.