組合數(shù)學(xué) 第三章學(xué)習(xí)資料

3.1某甲參加一種會(huì)議,會(huì)上有6位朋友,某甲和其中每一個(gè)人在會(huì)上各相遇12次,每?jī)扇烁飨嘤?次,每3人各相遇4次,每4人各相遇3次,每5人各相遇2次,每6人各相遇1次,1人也沒(méi)遇見的有5次,問(wèn)某甲共參加幾次會(huì)議?解:設(shè)A為甲與第i個(gè)朋友相遇的會(huì)議集.i=1,2,3,4,5,6.則│∪A│=12*C(6,1)-6*C(6,2)+4*C(6,3)-3*(6,4)+2*(6,5)-C(6,6)=28甲參加的會(huì)議數(shù)為28+5=333.2：求從1到500的整數(shù)中被3和5整除但是不能被7整除的數(shù)的個(gè)數(shù)。解：設(shè) A3：被3整除的數(shù)的集合A5：被5整除的數(shù)的集合A7：被7整除的數(shù)的集合所以|A7=|A5∩A=5003×5-5003.3n個(gè)代表參加會(huì)議，試證其中至少有2個(gè)人各自的朋友數(shù)相等解：每個(gè)人的朋友數(shù)只能取0，1，…，n－1．但若有人的朋友數(shù)為0，即此人和其他人都不認(rèn)識(shí)，則其他人的最大取數(shù)不超過(guò)n－2．故這n個(gè)人的朋友數(shù)的實(shí)際取數(shù)只有n－1種可能．，根據(jù)鴿巢原理所以至少有２人的朋友數(shù)相等．×3.4試給出下列等式的組合意義證明：（1）從n個(gè)不同元素中取k，使得其中必含有m個(gè)特定元素的方案數(shù)為。設(shè)這m個(gè)元素為a1,a2,…,am,Ai為包含ai的組合（子集），i=1,…,m.（2）把l個(gè)無(wú)區(qū)別的球放到n個(gè)不同的盒子，但有m個(gè)空盒子的方案數(shù)為令k=n-m，設(shè)Ai為第i個(gè)盒子有球，i=1，2，…k（3）設(shè)Ai為m+l個(gè)元素中去m+i個(gè)，含特定元素a的方案集；Ni為m+l個(gè)元素中取m+i個(gè)的方案數(shù)。則：3.5設(shè)有3個(gè)7位的二進(jìn)制數(shù)試證存在整數(shù)和，使得下列之一必然成立：解：應(yīng)用鴿巢原理，在每一個(gè)縱列中，含有三個(gè)元素，分別都只由兩種選擇0或1，應(yīng)用鴿巢原理所以必有中至少一個(gè)必然成立；成立的時(shí)候取值的不同可以有這樣幾種情況：=6種，而每一橫行共有七個(gè)元素，再次用鴿巢原理，必有兩列是相同的即：之一必然成立3.6在邊長(zhǎng)為1的正方形內(nèi)任取5點(diǎn)，試證其中至少有兩點(diǎn)，其距離小于。證明：分別連接對(duì)邊的中點(diǎn)，這樣正方形被均勻的分成四個(gè)域，在正方形內(nèi)任取5點(diǎn)，根據(jù)鴿巢原理，至少有兩點(diǎn)在同一個(gè)域中，而一個(gè)域內(nèi)兩點(diǎn)的最遠(yuǎn)距離小于，所以至少存在兩點(diǎn)其距離小于。3.7在邊長(zhǎng)為1的等邊三角形內(nèi)任取5點(diǎn)，試證至少有兩點(diǎn)距離小于。證明：將邊長(zhǎng)為1的等邊三角行分成4等份，如圖。則至少有兩個(gè)點(diǎn)在同一個(gè)小三角行中，每個(gè)小三角形的邊長(zhǎng)為，所以至少存在兩個(gè)點(diǎn)見的距離小于。3.8．任取11個(gè)整數(shù)，求證其中至少有兩個(gè)數(shù)它們的差是10的倍數(shù)。解：易知任意整數(shù)的個(gè)位數(shù)的可能取值只可能為，共10種可能，而利用鴿巢原理，任取的11個(gè)整數(shù)中，其中至少有兩個(gè)整數(shù)的個(gè)位數(shù)相同，這兩個(gè)個(gè)位數(shù)相同的整數(shù)的差顯然是10的倍數(shù)。即證。×3.9把從1到326的326個(gè)整數(shù)任意分為5個(gè)部分，試證其中有一部分至少有一個(gè)數(shù)是某兩個(gè)數(shù)之和，或是另一個(gè)數(shù)的兩倍。解：用反證法。設(shè)存在劃分，Pi中沒(méi)有數(shù)是兩數(shù)之和，即Pi中沒(méi)有數(shù)是兩數(shù)之差。設(shè)1到326中至少有個(gè)元素屬于P1，并設(shè)為，不妨設(shè)，若A中存在一個(gè)元素是某兩個(gè)元素之差，則滿足要求。否則，令，令，顯然B中的元素仍然是1到326之間的數(shù)，即。根據(jù)假定B中無(wú)一屬于P1，否則與假定矛盾。所以B的元素屬于P2，P3，P4，P5。與前面討論類似，設(shè)B中至少存在屬于P2的個(gè)元素。設(shè)為。令。根據(jù)假定，C中沒(méi)有數(shù)是兩數(shù)之差。令，，那么，對(duì)于所有。易知存在整數(shù)使得。所以，D中的元素不屬于P1，也不屬于P2，只能屬于P3，P4，P5。故根據(jù)鴿巢原理，設(shè)至少存在個(gè)元素屬于P3。設(shè)為。令。根據(jù)假定，F(xiàn)中不存在元素是某兩個(gè)元素之差，令。顯然G中的元素不屬于P3。且，對(duì)于gi存在使得。故G中的元素也不屬于P1和P2。則G中的元素屬于P4，P5。對(duì)于G中的5個(gè)元素，根據(jù)鴿巢原理，設(shè)至少存在個(gè)屬于P4。設(shè)為。令。令。顯然，T中的元素不屬于P1，P2，P3，P4，故T的元素屬于P5。但根據(jù)假定，令，則且u不屬于P5。同樣，u不屬于P1，P2，P3，P4，即存在一個(gè)整數(shù)，不屬于P1，P2，P3，P4，P5。這與將1至326之間的整數(shù)任意分為5部分的假定相矛盾。A,B,C三種材料用作產(chǎn)品1，2，3的原料，但要求1禁止用B和C作原料，2不能用B作原料，3不允許用A作原料，問(wèn)有多少種安排方案？（假定每種材料只做一種產(chǎn)品的原料）。解：此問(wèn)題為有禁區(qū)的排列可轉(zhuǎn)化為棋盤多項(xiàng)式求解如圖所示：P=R（）=XR（）+R（）=1+4x+4+=4,=4,=1根據(jù)定理：n!-(n-1)!+(n-2)!-(n-3)!……故方案為：3！-4（3-1）！+4（3-2）！-1=13.11n個(gè)球放到m個(gè)盒子中去，，試證其中必有兩個(gè)盒子有相同的球數(shù)。題解：設(shè)m個(gè)盒子的球的個(gè)數(shù)是a1,…,am，各不相等，且有0≤a1＜a2＜···＜am．則有a2≥1、am≥m－1，故

≥1+2+…+m－1＝，與相矛盾！所以必有兩個(gè)盒子的球數(shù)相等．×3.12一年級(jí)有100名學(xué)生參加中文，英語(yǔ)和數(shù)學(xué)考試，其中92通過(guò)中文考試，75人通過(guò)英語(yǔ)考試，65人通過(guò)數(shù)學(xué)考試；其中65人通過(guò)中，英文考試，54人通過(guò)中文和數(shù)學(xué)考試，45人通過(guò)英語(yǔ)和數(shù)學(xué)考試，求通過(guò)3門學(xué)科考試的學(xué)生數(shù)。題解：設(shè)A為通過(guò)中文的人數(shù)，B為通過(guò)英語(yǔ)的人數(shù)，C為通過(guò)數(shù)學(xué)的人數(shù)。試證1|B|=|B|-|AB|2|C|=|C|-|AC|-|BC|+|ABC|證：設(shè)全集為S|B|=|（S-A）B|=|SB|-|AB|=|B|-|AB|同理可證|C|=|C|-|AC|-|BC|+|ABC|3.14，求其中不被5和7除盡，但被3除盡的數(shù)的數(shù)目。解：設(shè)U表示全集，A3表示能被3除盡的數(shù)的集合，A5表示能被5除盡的數(shù)的集合，A7表示能被7除盡的數(shù)的集合。則所求的是。，，，，，同理，所以，3.15．，求其中被2，3，5，7中m個(gè)數(shù)除盡的數(shù)的數(shù)目，m=0,1,2,3,4.求不超過(guò)120的素?cái)?shù)的數(shù)目。解：不超過(guò)120的素?cái)?shù)數(shù)目即為：3.16解：3.17n除盡中至少一個(gè)數(shù)的除數(shù)，求n的數(shù)目解：A：的約數(shù)B：的約數(shù)C：的約數(shù)|A|=61×61=3721|B|=101×51=5151|C|=41×31=1271=61×51=3111=41×41=1681=41×41=1681=41×41=1681=5351×3.18求下列集合中不是形式的數(shù)的數(shù)目，。解：BC內(nèi)元素為1…100000通過(guò)程序驗(yàn)證既是2次方又是3次方的即為所求解：即為所求3.19{1000，1001，…，3000}，求其中是4的倍數(shù)但不是100的倍數(shù)的數(shù)的數(shù)目。解：A為4的倍數(shù)的整數(shù)B為100的倍數(shù)的整數(shù)|A∩B|=|A|-|A∩B|=3000-10004×3.20在由a,a,a,b,b,b,c,c,c組成的排列中，求滿足下列條件的排列數(shù) （1）不存在相鄰3元素相同 （2）相鄰兩元素不相同解：（1）設(shè)S為總共的排列數(shù)，為3個(gè)a相鄰的排列，為3個(gè)b相鄰的排列， 為3個(gè)c相鄰的排列； 所以不存在相鄰3元素相同為=（2）設(shè)S為總的排列數(shù)，為2個(gè)以上a相鄰的排列，為2個(gè)以上b相鄰的排列， 為2個(gè)以上c相鄰的排列； 所以不存在相鄰3元素相同為=×3.21：求從O（0，0）點(diǎn)到（8，4）點(diǎn)的路徑數(shù)。已知（2，1）到（4，1）的線段，（3，1）到（3，2）的線段被封鎖。解:由題意設(shè) A1：從(0,0)點(diǎn)到(8,4)點(diǎn)經(jīng)過(guò)(2,1)到(3,1)的線段.A2：從(0,0)點(diǎn)到(8,4)點(diǎn)經(jīng)過(guò)(3,1)到(3,2)的線段.A3：從(0,0)點(diǎn)到(8,4)點(diǎn)經(jīng)過(guò)(3,1)到(4,1)的線段.從(0,0)點(diǎn)到(8,4)點(diǎn)經(jīng)過(guò)(2,1)到(4,1)的線段，根據(jù)乘法原理|A1|=C(1,2+1)*C(4-1,8-3+|A2|A3|A1|A1|A2|A1|A1∩A2∩A3|=C(4,12)-(|A1|+|A2|+|A=495-(168+84+140)+(105+63+0)-0=2713—22求滿足條件x+x+x=20,3≤x≤9,0≤x≤8,7≤x≤17的整數(shù)解數(shù)目.解:作變量代換a=x-3,b=x,c=x-70≤a≤6,0≤b≤8,0≤c≤10則方程變?yōu)閍+b+c=10設(shè)s為這個(gè)方程的非負(fù)整數(shù)解集合∣s∣=C(10+3-1,10)=66設(shè)p為性質(zhì)a≥7,p為性質(zhì)b≥9,p為性質(zhì)c≥11令A(yù)為s中滿足性質(zhì)p(i=1,2,3)的集合,則問(wèn)題歸結(jié)為求∣A∩A∩A∣.可求得是方程a+b+c=10(a≥7,b≥0,c≥0)的整數(shù)解集合,通過(guò)作代換z=a-7,z=b,z=c可得∣A∣=C(3+3-1,3)=10,類似可得∣A∣=C(1+2,1)=3,∣A∣=0∣A∩A∣=0∣A∩A∣=0∣A∩A∣=0∣A∩A∩A∣=0∣A∩A∩A∣=66-13=533.23求滿足下列條件X1+X2+X3=206<=X1<=15,5<=X1<=20,10<=X1<=25解：設(shè)y1=x1-6.y2=x2-5,y3=x3-10,則有y1+y2+y3=x1+x2+x3-21=19設(shè)r1=9-y1,r2=15-y2,r3=25-y3則有r1+r2+r3=49-(y1+y2+y3)=49-19=20即r1+r2+r3=20r1>=0,r2>=0,r3>=0解的數(shù)目為3．24求滿足下列條件的整數(shù)解數(shù)目：，，，，解：設(shè)，，，，則有，，，則該問(wèn)題的非負(fù)整數(shù)解S，，令S中具有的子集為，的子集為，的子集為，的子集為。問(wèn)題轉(zhuǎn)化為求。對(duì)于，相當(dāng)于或具有性質(zhì)的非負(fù)整數(shù)解的數(shù)目為同理，，，，，，，，，3.25證明滿足下列條件：+++=r()的整數(shù)解數(shù)目為答案： 設(shè)為{} 由 得： 推出： = =3.26試證滿足下條件：的整數(shù)解為證明：設(shè)∴∴整數(shù)解為×3.27求n對(duì)夫妻排成一行，夫妻不相鄰的排列數(shù)。解：令=第i對(duì)夫妻相鄰而坐的集合，，所問(wèn)的問(wèn)題為求=（圓桌）×3.28設(shè)p,q,p是奇數(shù),現(xiàn)有pq個(gè)珠子,著q種顏色,每種顏色有p個(gè)珠子，假定相同顏色的珠子無(wú)區(qū)別，試分別求滿足以下條件的珠子的排列數(shù)。同顏色的珠子在一起同顏色的珠子處于不同的塊同顏色的珠子最多在兩個(gè)塊解：1）由于是同顏色的珠子放在一起，有q！種方案。2）3）3.29將r個(gè)相同的球放進(jìn)n個(gè)不同的盒子，無(wú)一空盒，求方案數(shù)。根據(jù)可重復(fù)組合公式，組合意義即是，將r個(gè)相同的球放進(jìn)n個(gè)不同的盒子，無(wú)一空盒，所以總方案數(shù)為(n+r-1r).×3.30

試證：證明：令表示第一個(gè)盒子為空；表示第二個(gè)盒子為空；表示第n個(gè)盒子為空表示從n個(gè)不同的盒子中取出i個(gè)為空盒，則剩下的n-i盒子不為空。=()表示的幾何意義是R個(gè)相同的球放入n個(gè)不同的盒子中，不許有空盒。表示的幾何意義是R個(gè)相同的球放入n個(gè)不同的盒子中，不許有空盒。幾何意義相同所證成立?！?.31設(shè)B是A的子集，|A|=n,|B|=m,求A的子集中包含B的數(shù)目，設(shè)子集的元素?cái)?shù)目為r,m≤r≤n。解：A的子集中包含B的那部分，即為在A-B中任取值的組合數(shù)，可為取1，2，3…….n-m個(gè)所以，A的子集中包含B的數(shù)目為。×3.32×3.33試證 （1） （2） 其中，定義為0. （3） （4） （5） （6） 是3.6節(jié)中推廣了的錯(cuò)排。證明：此題可由組合含義證明。等式左邊：相當(dāng)于從ｎ個(gè)不同元素中?。騻€(gè)進(jìn)行排列，其中只有ｋ個(gè)元素在原來(lái)的位置這樣的方案數(shù)，為。等式右邊：相當(dāng)于首先在ｒ個(gè)元素中?。雮€(gè)元素，為，然后在n-r個(gè)元素中取r-k個(gè)，對(duì)r-k個(gè)元素進(jìn)行完全錯(cuò)排，為，故總的方案數(shù)為。左右兩端顯然相等，證畢。（５）此題可由組合含義證明。從ｎ個(gè)不同元素中取ｒ個(gè)進(jìn)行排列，其中只有ｋ個(gè)元素在原來(lái)的位置的方案數(shù)（）可以分為兩種情況：即是否包含元素ａ（ａ為任意元素）。第一種情況是包含元素ａ，則只需在剩下的n-1個(gè)元素中取r-1個(gè)即可，然后進(jìn)行只有ｋ個(gè)元素不變的錯(cuò)排，方案數(shù)為；第二種情況是不包括元素ａ，則需要在剩下的n-1個(gè)元素中?。騻€(gè)元素，進(jìn)行只有ｋ個(gè)元素不變的錯(cuò)排，方案數(shù)為。所以總的方案數(shù)為：，即，證畢?！?.34,設(shè)表示在{1，2，…，n}的全排列中，排除了k，緊隨以k+1,k=1,2,…,k+1，試證：解：×3.35×3.36設(shè)Dn(k)=D(n,n,k),試證 （a）（b）Dn(0)-Dn(1)=(-1)n（c）…（d）其中r≤n。3．37

試證對(duì)于素?cái)?shù)，，證明：根據(jù)定理若=是素?cái)?shù)所證成立?！?.38試證：（1）n=∑d|nΦ(n)(2)Φ(m,n)Φ(n)=Φ(m)Φ(n)h,其中m,n∈N,h=(m,n)(3)n∈N,n>=3,Φ(n)通常是偶數(shù)。解：（1）因?yàn)棣?n)=n∑d|nμ(d)/d所以Φ(n)=∑d|nμ(d)n/d所以我們?cè)O(shè)n=f(n),Φ(n)=g(n)根據(jù)反演定理，可得n=∑d|nΦ(n).（2）因?yàn)棣?m,n)=mn∑d1,d2|m,nμ(d1,d2)/d1,d2根據(jù)第一問(wèn)，可得必然存在一個(gè)中間的數(shù)h,使得Φ(m,n)Φ(n)=Φ(m)Φ(n)h,其中m,n∈N,h=(m,n)成立。×3.39n，證明若n有k個(gè)不同的奇偶因子，則（1）（2）（3），n是奇數(shù)，n是偶數(shù)解：此題不會(huì)?！?.40從集合中隨機(jī)抽取28次，求出現(xiàn)塊的幾率。解：3.42一組有1990個(gè)人，每個(gè)人至少有1327個(gè)朋友，試證其中4位，使得彼此都是朋友。答案： 從1990中取出一個(gè)人a，剩下1989個(gè)人，則這個(gè)人a至少認(rèn)識(shí)1989中的1327個(gè)人，定義為friend1，還剩下1989-1327=662個(gè)人不認(rèn)識(shí)定義為strenge1。如果在a認(rèn)識(shí)的1327個(gè)人中又存在一個(gè)人b，他也認(rèn)識(shí)的人也為1327個(gè)，因?yàn)閒riend1中只有662個(gè)人所以，b認(rèn)識(shí)的人中一定有至少兩個(gè)在a認(rèn)識(shí)的friend1里，所以至少有4位彼此是朋友！3．43邊長(zhǎng)為1的等邊三角形內(nèi)任意5個(gè)點(diǎn)，至少有兩點(diǎn)，其間距離最多為1/2。解：把邊長(zhǎng)為1的等邊三角形分成四個(gè)邊長(zhǎng)為1/2的等邊三角形，如圖所示則根據(jù)鴿巢原理，這五點(diǎn)中必有兩點(diǎn)落在同一個(gè)邊長(zhǎng)為1/2的等邊三角形中。而邊長(zhǎng)為1/2的等邊三角形中任意兩點(diǎn)間的距離都小于1/2。3—45邊長(zhǎng)為1的正方形內(nèi)任取9點(diǎn),試證存在3個(gè)不同的點(diǎn),由此構(gòu)成的三角形面積不超過(guò)1/8.解:如下圖.把1×1的正方形分成四個(gè)(1/2)× (1/2)的正方形,根據(jù)鴿巢原理,((10-1)/4)+1=3,則這10點(diǎn)中必有三點(diǎn)落在同一個(gè)小正方形中,而小正方形內(nèi)的任三點(diǎn)構(gòu)成三角形面積最大為1/8.所以構(gòu)成的三角形面積不超過(guò)1/8.3.46：給任何5個(gè)整數(shù)，試證必存在3個(gè)數(shù)的和被3除盡。解：所有整數(shù)可分為3類，mod3=0,mod3=1,mod3=2，分別標(biāo)記為A,B,C.如果在這五個(gè)數(shù)中，任何一類的個(gè)數(shù)大于等于3，那么在這個(gè)類中任取三個(gè)元素，它們的和一定能被三整除。如果沒(méi)有任何一類的個(gè)數(shù)大于等于3，那么只能是2，2，1的組合.如果A類元素只有一個(gè)，那么B類，C類各有2個(gè)元素。A，B，C各類各取一個(gè)，它們的和一定能被三整除。如果B類元素只有一個(gè)，那么A類，C類各有2個(gè)元素。A，B，C各類各取一個(gè)，它們的和一定能被三整除。如果C類元素只有一個(gè)，那么A類，B類各有2個(gè)元素。A，B，C各類各取一個(gè)，它們的和一定能被三整除。3.47A是n+1個(gè)數(shù)的集合，試證其中必存在兩個(gè)數(shù)，它們的差被n除盡。 解：如果n+1個(gè)元素有相同的值，那么命題自然得證 如果每?jī)蓚€(gè)元素之間都有不同的值，那么如下假設(shè)a為集合中最小的數(shù)，現(xiàn)在有值為0，1，2，…，n-1個(gè)盒子，現(xiàn)在對(duì)于A中的每個(gè)數(shù)進(jìn)行如下運(yùn)算 K=把放入K值對(duì)應(yīng)的盒子當(dāng)中，所以根據(jù)鴿巢原理，必有一個(gè)盒子內(nèi)有兩個(gè)元素，不妨設(shè)為和，因?yàn)樗麄儩M足=，所以和滿足，所以一定存在兩個(gè)元素的差被n除盡3.48A={a1，a2，…，a2k+1}，k≥1，ai是正整數(shù)，k=1，2，…，2k+1，試證A的任意排列：恒有為偶數(shù)證明：另n=|A|=2k+1，則A中奇數(shù)和偶數(shù)個(gè)數(shù)不相等。如果中全為“奇數(shù)-偶數(shù)”或“偶數(shù)-奇數(shù)”的形式，則A中奇數(shù)和偶數(shù)個(gè)數(shù)相等，與前面矛盾。顧中必有“奇數(shù)-奇數(shù)”或“偶數(shù)-偶數(shù)”的形式，即為偶數(shù)。3.49A是中任意n+1個(gè)數(shù)，試證明至少存在一對(duì)，使下面結(jié)果成立：解：假設(shè)取出任意n+1個(gè)數(shù)，將它們每一個(gè)都拆成2的幾次冪乘以一個(gè)奇數(shù)的形式；那么一共能拆出n+1個(gè)奇數(shù)（每個(gè)數(shù)對(duì)應(yīng)一個(gè)奇數(shù)）。然而，在上述A集合之中，2n個(gè)元素一共只有n個(gè)奇數(shù)。所以根據(jù)鴿巢原理，能夠得出上述n+1個(gè)奇數(shù)中至少有兩個(gè)是相等的。而這兩個(gè)數(shù)必然一個(gè)能被另一個(gè)整除?！档米C?！?.51×3.52．空間2n個(gè)點(diǎn)，，試證用條線段任意連接這2n個(gè)點(diǎn)，必然出現(xiàn)一個(gè)三角形，并證明用條線連接，則可能不出現(xiàn)三角形。解：將這2n個(gè)點(diǎn)分成兩個(gè)集合，,，則使得A中每個(gè)點(diǎn)都與B中每個(gè)點(diǎn)都有一條邊相連，總的需要的邊數(shù)為ab,易知當(dāng)a=b=n時(shí)需要的邊數(shù)最多且為,又因?yàn)榭偣灿袟l線段，則在集合A,B中一定存在某兩個(gè)點(diǎn)之間有邊，即證必然出現(xiàn)一個(gè)三角形。當(dāng)a=b=n時(shí)，用條線段相連時(shí)，上述情況則不出現(xiàn)三角形?！?.53三維空間中9個(gè)坐標(biāo)為整數(shù)的點(diǎn)，試證在兩兩相連的線段內(nèi)，至少有一個(gè)坐標(biāo)為整數(shù)的內(nèi)點(diǎn)。解：三維空間中，任意兩坐標(biāo)為整數(shù)的點(diǎn)，若這兩點(diǎn)相連的線段內(nèi)不存在坐標(biāo)為整數(shù)的內(nèi)點(diǎn)，則對(duì)于x,y,z這三個(gè)坐標(biāo)軸，這兩點(diǎn)至少在一個(gè)坐標(biāo)上的差值正好是1。那么，在這9個(gè)坐標(biāo)為整數(shù)的點(diǎn)中，任取一點(diǎn)，與這個(gè)點(diǎn)的三個(gè)坐標(biāo)中，存在差值正好是1的共有7類，即：與x軸差值正好是1，與y軸差值正好是1，與z軸差值正好是1，與x,y軸差值都是1，與x,z軸差值都是1，與y,z軸差值都是1，與x,y,z軸差值都是1。那么，對(duì)于剩下的8個(gè)點(diǎn)，若存在一點(diǎn)a不滿足這7種情況，那么a點(diǎn)與這個(gè)點(diǎn)相連的線段內(nèi)必有一個(gè)坐標(biāo)為整數(shù)的內(nèi)點(diǎn)。若剩下的8個(gè)點(diǎn)都屬于這7種情況之一，那么，運(yùn)用鴿巢原理，則至少存在兩個(gè)點(diǎn)屬于這7種情況中的同一個(gè)情況，那么，這兩點(diǎn)中必存在一個(gè)坐標(biāo)為整數(shù)的內(nèi)點(diǎn)。二維空間的（x,y）點(diǎn)的坐標(biāo)x和y都是整數(shù)的點(diǎn)稱為格點(diǎn)。任意5個(gè)格點(diǎn)的集合A，試證A中至少存在兩點(diǎn)，它們的中點(diǎn)也是格點(diǎn)。解：集合A={（,）,(,),(,),(,),(,)},均為整數(shù)（,）有四種情況，分別是：奇偶，偶奇，奇奇，偶偶。問(wèn)題就轉(zhuǎn)化為（，）也為整數(shù)。即（,）也為整數(shù)5個(gè)點(diǎn)，4種情況，根據(jù)鴿巢原理必有兩個(gè)點(diǎn)是相同類型又因?yàn)槠?奇=偶，偶+偶=奇，故得證?！?.55令A(yù)為從等差數(shù)列1，4，7，10…100中選擇20個(gè)不同的數(shù)，試證其中至少存在兩個(gè)數(shù)，他們的和為100.題解：假設(shè)20個(gè)數(shù)中任意兩個(gè)數(shù)的和都不為104an+bm≠104即1+(n-1)3+1+(m-1)3≠104即n+m≠341≤n≤20,1≤m≤202≤n+m≤40即n+m可以為34即矛盾，成立?！?.56平面上6個(gè)點(diǎn)，不存在3點(diǎn)共一條直線，其中必存在3點(diǎn)構(gòu)成一個(gè)三角形，有一內(nèi)角小于30°。題解：這道題是Ramsey數(shù)的變形，三點(diǎn)構(gòu)成一個(gè)三角，某個(gè)點(diǎn)對(duì)應(yīng)的這個(gè)角度>30或<=30就相當(dāng)于三個(gè)人之間是相互認(rèn)識(shí)或是相互不認(rèn)識(shí).反證法:假設(shè)題設(shè)不成立.即所有構(gòu)成的角度都>30度;假設(shè)1分別與23456(不妨設(shè)順時(shí)針圍繞在1周圍)的夾角都>30度,則總度數(shù)>150;合理;繼續(xù):三角形124中1點(diǎn)的度數(shù)>60;又因?yàn)?>30且4>30則三內(nèi)角和>180,矛盾,得證!×3.57n是大于等于3的整數(shù)，則下列數(shù)的集合{2-1，-1，-1，……，-1}中存在一數(shù)被n除進(jìn)。答：此題出錯(cuò)，A集合中不滿足被2的倍數(shù)的n除盡，例如n=6>3,但不滿足題設(shè)。×3.58n個(gè)人的集體，試證存在兩個(gè)人，在余下的n-2個(gè)人中，至少有個(gè)要么與二人互相認(rèn)識(shí)，要么與這兩個(gè)人均不認(rèn)識(shí)?！?.59．,A和B是S的不相交子集。若A和B的元素之和不等，即屬于A的元素之和不等于屬于B的元素之和，試證×3.60下列m*n矩陣的元素是實(shí)數(shù)每行的最大元素與最小元素之差不超過(guò)d>0.對(duì)梅列元素重新排列成遞減序列，即最大元素在第一行，最小元素在第m行，是證明經(jīng)過(guò)重新排列后的矩陣，每行最大元素與最小元素之差仍然不超過(guò)d。3.61n個(gè)單位各派兩名代表出席一個(gè)會(huì)議，2n位代表圍著一圓桌坐下，試問(wèn)各單位的代表并排坐著的方案有多少？各單位的兩人互不相鄰的方案數(shù)又等于多少？解：(1).（2）.令第i個(gè)單位的代表相鄰而坐的集合，===故各單位的兩人互不相鄰的方案數(shù)：3.62一層書架有m層，分別放置m類不同種類的書，每層n冊(cè)，現(xiàn)將書架上的圖書全部取出清理，清理過(guò)程中要求不打亂所在的類別。試問(wèn)：m類書全不在各自原來(lái)層的方案數(shù)有多少？解：m個(gè)對(duì)象的錯(cuò)排問(wèn)題：每層的n本書都不在原來(lái)的位置上的方案數(shù)等于多少？解：如果某類書不在原來(lái)的層上，則對(duì)該層的n本書全排列即可；如果某類書在原來(lái)的層上，則對(duì)n本書進(jìn)行錯(cuò)排即可：m層書都不在原來(lái)層次，每層n本書也不在原來(lái)位置上的方案數(shù)？解：3.63(m+1)行mm+12+1證：每列有(m+1)行，只有m種顏色，故一列中必有兩格同色．同色的２個(gè)格子的行號(hào)有m+12種取法．有m種色，故有mm+12種同色模式，現(xiàn)有3.64兩名教師分別對(duì)6名學(xué)生進(jìn)行面試（每位教師各負(fù)責(zé)一門課），每名學(xué)生面試時(shí)間固定，試問(wèn)共有多少種面試的順序。 解：先對(duì)第一門課的學(xué)生進(jìn)行排列，然后再排第二門課的順序，那么第二門課程的排序就將成為一個(gè)錯(cuò)排問(wèn)題，對(duì)每一個(gè)第一門課的排列，都對(duì)應(yīng)一系列的錯(cuò)排，即如下第一門課的順序有6!種；

第二門課的順序有（根據(jù)例3-10，錯(cuò)排問(wèn)題）：D6＝6!((1/2!)－(1/3!)＋(1/4!)－(1/5!)＋(1/6!))＝265;

故總順序有6!×265種．3.65：X={0，1，2，3……9，10}從X中任意取7個(gè)元素，則其中必有兩個(gè)元素之和等于10.解：|X|=11，分為6組{0,10},{1,9},{2,8},{3,7},{4,6},{5}.從這11個(gè)數(shù)中去7