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

1、1.某甲參加一種會議，會上有6位朋友，某甲和其中每人在會上各相遇12次，每二人各相遇6次，每三人各相遇3次，每五人各相遇2次，每六人各相遇一次，1人也沒有遇見的有5次，問某甲共參加了幾次會議,解：...,第三章習(xí)題解答,2.求從1到500的整數(shù)中被3和5整除但不被7整除的數(shù)的個(gè)數(shù).,解：...,第三章習(xí)題解答,3. n代表參加會議，試證其中至少有2人各自的朋友數(shù)相等。,解：...,第三章習(xí)題解答,4. 試給出下列等式的組合意義,第三章

2、習(xí)題解答,解：...,第三章習(xí)題解答,5.設(shè)有3個(gè)7位的2進(jìn)制數(shù),解：...,試證存在整數(shù)i和j， 使得下列之一必然成立。,第三章習(xí)題解答,6. 在邊長為1的正方形內(nèi)任取5個(gè)點(diǎn)試證其中至少有兩點(diǎn)，期間距離小于,解：...,第三章習(xí)題解答,7.在邊長為1的等邊三角形內(nèi)任取5個(gè)點(diǎn)試證其中至少有兩點(diǎn)，期間距離小于,解：...,第三章習(xí)題解答,8. 任取11個(gè)整數(shù)，求證其中至少有兩個(gè)數(shù)它們的差是1

3、0的倍數(shù)。,解：...,第三章習(xí)題解答,9. 把從1到326的326個(gè)整數(shù)任意分為5個(gè)部分，試證其中有一部分至少有一個(gè)數(shù)是某兩個(gè)數(shù)之和，或是另一個(gè)數(shù)的兩倍。,解：...,第三章習(xí)題解答,10. A、B、C三種材料用作產(chǎn)品I、II、III的原料，但要求I禁止用B、C作原料，II不能用B作原料，III不允許用A作原料，問有多少種安排方案？（假定每種材料只做一種產(chǎn)品的原料）,解：...,第三章習(xí)題解答,11. n個(gè)球放到m個(gè)盒子中去，

4、試證其中必有兩個(gè)盒子有相同的球數(shù)。,解：...,第三章習(xí)題解答,12. n各單位各派兩名代表去出席一會議。 位代表圍一圓桌坐下。試問： （1）各單位代表并排坐著的方案是多少？（2）各單位的兩人互不相鄰的方案數(shù)又是多少？,解：...,第三章習(xí)題解答,13. 一書架有m層，分別放置m類不同種類的書，每層n冊。先將書架上的圖書全部取出清理。清理過程要求不打亂所有的類別。試問（1）m類書全不在各自原來層次上的方案數(shù)

5、有多少？（2）每層的n本書都不在原來位置上的方案數(shù)等于多少？（3）m層書都不在原來層次，每層n本書也不在原來位置上的方案數(shù)又有多少？,解：...,第三章習(xí)題解答,14. 行 列 的格子同種顏色著色，每格趙一種顏色，其中必有一個(gè)4角同色的矩形。,解：...,第三章習(xí)題解答,15. 兩名教師分別對6名學(xué)生同時(shí)進(jìn)行兩門課程的面試（每名教師各管一門課程）每名學(xué)

6、生每門面試的時(shí)間都是半個(gè)小時(shí)，共有多少不同的面試順序？,解：...,第三章習(xí)題解答,16. 在平面直角坐標(biāo)系中至少任去多少個(gè)整點(diǎn)（兩個(gè)坐標(biāo)系都是整數(shù)）才能保證其中存在3個(gè)構(gòu)成三角形（包含3點(diǎn)在一條直線上）的面積是整數(shù)（可以為0）,解：...,第三章習(xí)題解答,17. 在平面直角坐標(biāo)系中至少任去多少個(gè)整點(diǎn)才能保證存在3個(gè)點(diǎn)構(gòu)成的三角形的重心是整點(diǎn)？,解：...,第三章習(xí)題解答,第三章習(xí)題解答,1．解　設(shè)Ai為甲與第i個(gè)朋友相遇的會議

7、集，i＝1，…，6．則｜∪Ai｜＝12 ( ) －6 ( )＋4 ( ) －3 ( )＋2 ( )－( ) ＝28故甲參加會議數(shù)為　　28＋5＝33 （題目）,61,62,63,64,65,66,第三章習(xí)題解答,２　解　設(shè)A3：被3整除的數(shù)的集合

8、 A5：被5整除的數(shù)的集合 A7：被7整除的數(shù)的集合所以｜A7∩A5∩A3｜＝｜A3∩A5｜－ ｜A7∩A5∩A3｜＝? 　 ?－? ?＝33－4＝29 （題目）,,500 3·5,5003·5·7,,,第三章習(xí)題解答,3　解　每個(gè)人的朋友數(shù)只能取0，1，…，n－1．但若有人的朋友數(shù)為0，即此人和其他人都不認(rèn)

9、識，則其他人的最大取數(shù)不超過n－2．故這n個(gè)人的朋友數(shù)的實(shí)際取數(shù)只有n－1種可能．? ?＝２，所以至少有２人的朋友數(shù)相等． （題目）,nn－1,,第三章習(xí)題解答,4 　解　( a ) 從n個(gè)元素中取k個(gè)元的組合，總含指定的m個(gè)元的組合數(shù)為( )=( )設(shè)這m個(gè)元為a1，a2，…，am，Ai為不含ai的組合(子集)，i=1，…，m．｜Ai｜= ( )｜Ai1∩

10、 Ai2∩···∩ Ail｜＝( )( )＝｜∩ Ai｜ ＝( ) + ∑ (－1) ∑ ｜∩ Aij ｜ ＝∑(－1) ( ) ( ),n－1 k,n－ l k,n－mn－k,nk,m,i=1,m,l=1,l,l,j=1,{i1,…,il}∈￠(m , l),l,m

11、k,n－ l k,m,l=0,n－mk－m,n－mn－k,第三章習(xí)題解答,( b )令k＝n－m．l個(gè)相同的球放入k個(gè)不同的盒子里．每盒不空的方案數(shù)為( )．設(shè)Ai為第i個(gè)盒子為空的方案集，i=1,2,…,k.| Ai |= ( ), | ∩ Ais | = ( )( )= | ∩Ai |= ( )

12、 + ∑ (－1) ∑ ｜∩ Ais ｜＝∑(－1) ( ) ( ),l－1k－1,k－1+l－1 l,l－1k－1,,k－j+l－1 l,k+l－1 l,{i1,…,ij}∈￠(k , j),j,s=1,j,s=1,k,i=1,k,j=1,j,k,j=0,j,kj,k－j+l－1 l,第三

13、章習(xí)題解答,l個(gè)相同的球放入n個(gè)不同的盒子里，指定的m個(gè)盒子為空，其他盒子不空的方案數(shù)為( ),l－1n－m－1,第三章習(xí)題解答,( c ) 設(shè)Ai為m+l個(gè)元中取m+i個(gè)，含特定元素a的方案集；Ni為m+l個(gè)元中取m+i個(gè)的方案數(shù)．則：　　　Ni＝( )| Ai |=( )， | Ai |=( )| Ai+1 |= |

14、Ai |=( )| Ai |= Ni－| Ai | i=0,1, … ,l．| A0 |=N0 －| A0 | =N0－| A1 |=N0－(N1－|A1| =N0－N1+N2－…+(－1) Nl (題目）,,,,m+lm+ i,m+l－1m+ i－1,m+l－1 m+ i,m+l－1 m+ i,l,第三章習(xí)題解答,5　證　顯然，每列中必有兩數(shù)字相同，共有(

15、 )種模式，有０或１兩種選擇．故共有( )·2種選擇． ( )·2=6．現(xiàn)有7列，? －? = 2．即必有２列在相同的兩行選擇相同的數(shù)字，即有一矩形，四角的數(shù)字相等．（題目）,32,32,32,76,第三章習(xí)題解答,6 證　把１×１正方形分成四個(gè)－×－的正方形．如下圖：,12,12,,,,則這５點(diǎn)中必有兩點(diǎn)落在同一個(gè)小正方形內(nèi)．而小正方

16、形內(nèi)的任兩點(diǎn)的距離都小于－?2,12,,（題目）,第三章習(xí)題解答,7 證　把邊長為１的三角形分成四個(gè)邊長為－的三角形，如下圖：,12,,,,,則這５點(diǎn)中必有兩點(diǎn)落在同一個(gè)小三角形中．,（題目）,第三章習(xí)題解答,8 證　整數(shù)的個(gè)位數(shù)的可能取值為０，１，…，９．共１０種可能．11個(gè)整數(shù)中必有２個(gè)數(shù)的個(gè)位數(shù)相同，即這兩個(gè)數(shù)之差能被１０整除．,（題目）,第三章習(xí)題解答,９　證　用反證法。設(shè)存在劃分 P1∪P2∪P3∪P4

17、∪P5＝[1，326]，Pi中無數(shù)是兩數(shù)只差．?　 ?＝66，則有一Pi中至少有66個(gè)數(shù)，A＝{ a1 ,…,a66} ，a1＜a2＜···＜a66 ，以下按書上174頁的例題證明可得．(題目),326 5,,第三章習(xí)題解答,10　解　按題意可得如下的帶禁區(qū)的棋盤其中有陰影的表示禁區(qū)．,,,,,,,,,,,,,,A B C,Ⅰ,Ⅱ,Ⅲ,禁區(qū)的棋子多項(xiàng)式為：,R(

18、 ) =R( ) R( ) =(1+x)(1+3x+x ) =1+4x+4x + x,,,,,,,,,故方案數(shù)＝3!－4·2!+4 ·1!－1 ·0!＝1,2,2,3,（題目）,第三章習(xí)題解答,11 證　設(shè)m個(gè)盒子的球的個(gè)數(shù)是a1,…,am，各不相等，且有0≤a1＜a2＜···＜am．則有a2≥1、am≥m－1，故∑ai

19、≥1+2+…+m－1＝－m(m－1)與n<－m(m－1)相矛盾！所以必有兩個(gè)盒子的球數(shù)相等．,12,12,i=1,m,（題目）,第三章習(xí)題解答,12 解　( 1 ) 方案數(shù)＝(n－1)！·2,n,( 2 )　設(shè)第i個(gè)單位的代表相鄰的方案集為Ai，i＝1,2 , … ,n．| ∩Ai |＝ ∑ (－1 ) ∑ | ∩ Ai | ＝∑ (－1) ( ) (2n

20、－k－1)! 2,n,n,n,i=1,k=0,k=0,I∈￠( n ,k),i∈I,nk,k,k,k,（題目）,第三章習(xí)題解答,13 解　令Dn＝n!(1－－ + －－···±－)( 1 )方案數(shù)＝Dm( n! ),11!,12!,1n!,m,( 2 ) ∑ ( ) Dk (n!) Dn,mk,k,m－k,k=0,m,( 3 ) Dm Dn,m,（題目）,第三章習(xí)題

21、解答,14 證　每列有(m+1)行，只有m種顏色，故一列中必有兩格同色．同色的２個(gè)格子的行號有( )種取法．有m種色，故有m( )種同色模式，現(xiàn)有m( ) +1列，必有兩列的同色模式相同．即由這兩列的對應(yīng)行上有４個(gè)格子同色，正好是一個(gè)矩形的４個(gè)角上的格子．得證． (題目),m+1 2,m+1 2,m+1 2,第三章習(xí)題解答,15 　解　第一門課的順序

22、有6!種　　　 　第二門課的順序有： D6＝6! ( －－－＋－－－＋－ )＝265古總順序有6!×265種．?。}目）,12!,13!,14!,15!,16!,第三章習(xí)題解答,16 解　任一點(diǎn)的坐標(biāo)（a , b）只有如下４種可能：(奇數(shù)，偶數(shù))、(奇數(shù)，奇數(shù))、(偶數(shù)，奇數(shù))、(偶數(shù)，偶數(shù))。因而5個(gè)點(diǎn)中必有兩個(gè)點(diǎn)模2的格式一樣．設(shè)2｜(x1－x2)，2｜(y1－y2)即x1－x2＝2ky

23、1－y2＝２l，則三角形面積S△＝－,1　1　1x1 x2 x3y1 y2 y3,0　　　　1 1x1－ x2 　x2　x3y1 － y2 y2 y3,,,12,＝－,12,,,0　1　1k x2 x3l y2 y3,＝,,,是整數(shù)．,（題目）,第三章習(xí)題解答,17 解　設(shè)(x，y)是整點(diǎn)，每個(gè)分量模3后有如下表的結(jié)果：,,,,,,(0，0) (0，1

24、) (0，2),(1，0) (1，1) (1，2),(2，0) (2，1) (2，2),若有３個(gè)點(diǎn)模３后的結(jié)果落在上表中的同一格中，則這３個(gè)點(diǎn)的重心是整點(diǎn)．,第三章習(xí)題解答,若有３點(diǎn)占滿一行，則３點(diǎn)重心是整點(diǎn)；　有３點(diǎn)占滿一列，則３點(diǎn)重心是整點(diǎn)；若存在一組均勻分布，則有3點(diǎn)重心是整點(diǎn)．由上表可知，若只有8個(gè)點(diǎn)，也不能保證有３點(diǎn)的重心是整點(diǎn)．（因?yàn)槿裘總€(gè)格子都有２點(diǎn)，則只占有４個(gè)格子，無法保

25、證上面的要求）,下面假設(shè)存在９個(gè)點(diǎn)，其中任３點(diǎn)的重心都不是整點(diǎn)．,第三章習(xí)題解答,則這9個(gè)點(diǎn)，至少占有?－?＝5個(gè)格子（因?yàn)槊扛裰凶疃嘤?個(gè)點(diǎn)，否則有3個(gè)點(diǎn)的重心為整點(diǎn)），每行最多有２格，又?－?=3 所以每行都有點(diǎn)．同理，每列都有點(diǎn)．,92,52,不妨設(shè)第一行2點(diǎn)，第二行2點(diǎn)，第三行1點(diǎn)前2 行有兩種模式：,,,,,或,,,,,這樣第三行的點(diǎn)無論在哪一列都構(gòu)成占滿,第三章習(xí)題解答,一列或構(gòu)成一組均勻分布．滿足前面說