PAGE1PAGE1清北學堂數(shù)學競賽輔導材組方法與抽屜原1設整數(shù)n≥4,a1,a2,…,an是區(qū)間(0,2nn不同的整數(shù)，證明存在集合{a1,a2,…,an}的一個子集它的所有元和能被2n整[證明]（1）n{a1,a2,…,ann不同的數(shù)屬于n-1集數(shù)ai,aj(i≠j)屬于同一集合，從而ai+aj=2n2n除；（2）若n∈{a1,a2,…,an}，不妨設an=n，從a1,a2,…,an-1(n-1≥3)中任意取3個數(shù)ai,aj,ak(ai,<aj<ak)，則aj-ai與ak-ai中至少有一個不被n整除否則ak-ai=(ak-aj)+(aj-ai)≥2n這與ak∈(0,2n)故a1,a2,…,an-1中必有兩個數(shù)之差不被n整除；不妨設a1與a2之差(a2-a1>0)不被n整除，考慮na1,a2,a1+a2,a1+a2+a3,…,a1+a2+…+an-1。則結(jié)論成立；若k奇數(shù)，則加上an=n結(jié)論成立。若這n個數(shù)中沒有一個被n整除，則它們除以n的余數(shù)只能取1,2,…,n-1這n-1個值，由抽屜原理知其中必有兩個數(shù)除以n的余數(shù)相同，它們之差被n整除，而a2-a1不被n整除，故這個差必為aj,ak-1中若干個數(shù)之和，同?。┛芍Y(jié)論成立原例 在n×n的方格表的每個小方格內(nèi)寫有一個非負整數(shù)，并且數(shù)之和不小于n。證明：表中所有數(shù)之和不小于1n2。2 計算各行的和、各列的和，這2n個和中必有最小的，不妨設第m行的和最小，記和為k，則該行中至少有n-k個0，這n-k個0所在的各列的和都不小于n-k從而這n-k列的數(shù)的總和不小于(n-k)2，其余各列的數(shù)的總和不小于k2，從而表中所有數(shù)的總和不小于(n-k)2+k2≥(nk2

1n22不變量原例3設正整數(shù)n122na,b,|a-|證明]設S是黑板上所有數(shù)的和始時和數(shù)是S=1+2+2n=n(2n+1)，這是一個奇數(shù)，因為|a-b|與a+b有相同的奇偶性，故整個變化過程中S的奇偶性不變，故最后結(jié)果為奇數(shù)。4a1a2,…,an中每一個是1或-1并且有S=a1a2a3a4+ana1a2a3=0.證明[證明]如果把a1,a2,…,an中任意一個ai換成-ai，因為有4個循環(huán)鄰的項都改變符號，S4并不改變，開始時S=0S≡0S≡0(mod4經(jīng)有限次變號可將每個ai都變成1而始終有S≡0(mod4)，從而有n≡0(mod4)，所以4|n。構(gòu)造例 是否存在一個無窮正整數(shù)數(shù)列a1,<a2<a3<…，使得對任意整A，數(shù)列

中僅有有限個素數(shù) ]存 n≥2時，若n≥|A|，則an+A均為|A|的倍數(shù)且大于|A|，不可能為素數(shù)A=±1a±1=(n!±1)?[(n!)2±n!+1]當≥3時均為合數(shù)。從而當A整數(shù)時，{(n!)3+A}中只有有限個素數(shù)。n6一個多面體共有偶數(shù)條棱，試證：可以在它的每條棱上標上一[證明]AB（因為棱總數(shù)為偶數(shù)A與B除ABA，B，指向它的箭頭數(shù)變成了偶數(shù)。如果這時仍有頂點，指向它的箭頭的箭頭數(shù)為偶數(shù)。命題成立染色7能否在5×5格表內(nèi)找到一條線路，它由某格中心出發(fā)，經(jīng)[解]不可能。將方格表黑白相間染色，不妨設黑格為13，為12個，如果能實現(xiàn)，因黑交替出現(xiàn)，黑數(shù)目應相等，得凸包的使給定平面點集A，能蓋住A最小的凸圖形，稱為A凸包。8試證：任何不自交的五邊形都位于它的某條邊的同一側(cè)。[證明]五邊形的凸五包是凸五邊形、凸四邊形或者是三角形，凸包92×2方格紙去掉一個方格余下的圖形稱為拐形，用這拐形去覆蓋5×7的方格板，每個拐形恰覆蓋3個方格，可以但-1-1-1-1111111-1-1-1-1111111-1-1-1- 將5×7方格板的每一個小1111111-1-1-1-12×(-2)+23×1=-1覆蓋KK8．圖論方例10生產(chǎn)由六種顏色的紗線織成的雙色布在所生產(chǎn)的雙色布中，[證明用點A1，A2，A3，A4，A5，A6表示六種顏色，若兩種顏色的出三條邊命題等價于由這些邊和點構(gòu)成的圖中有三條邊兩兩不相相鄰，設為A1A2，A3A4。A5A6連有一條邊A1A2，A3A4，A5A6對應的三種雙A5A6之間沒有邊相連，不妨設A5和A1相連，A2A