本文格式為Word版，下載可任意編輯——組合數學第三章答案3.1題（宗傳玉）

某甲參與一種會議，會上有6位朋友，某甲和其中每人在會上各相遇12次，每二人各相遇6次，每三人各相遇3次，每五人各相遇2次，每六人各相遇一次，1人也沒有遇見的有5次，問某甲共參與了幾次會議解:

設Ai為甲與第i個朋友相遇的會議集，i＝1，…，6．則

故甲參與的會議數為:28+5=33.3.2題（宗傳玉）

求從1到500的整數中被3和5整除但不被7整除的數的個數.解:

設A3：被3整除的數的集合A5：被5整除的數的集合A7：被7整除的數的集合所以

3.3.題（宗傳玉）

n個代表參與會議，試證其中至少有2人各自的朋友數相等。解:

每個人的朋友數只能取0，1，…，n－1．但若有人的朋友數為0，即此人和其他人都不認識，則其他人的最大取數不超過n－2．故這n個人的朋友數的實際取數只有n－1種

可能．，所以至少有２人的朋友數相等．

3.4題（宗傳玉）

試給出以下等式的組合意義.

解:

(a)從n個元素中取k個元素的組合，總含有指定的m個元素的組合數為(設這m個元素為a1,a2,…,am,Ai為不含ai的組合（子集），i=1,…,m.

Ai1n?mk?m)?(n?mn?k)。

?Ai21???Ami1?n?l??????k??ml?n?m???????n?k?m?i?1Ai?n????????k??l?1(?1)l?(i1,...,il)??(m,l)?j?1Aij

????1?l?0l?m???k??n?l?????????k?

3.5題（宗傳玉）

設有三個7位的二進制數：a1a2a3a4a5a6a7，b1b2b3b4b5b6b7，c1c2c3c4c5c6c7．試證存在整數i和j，1≤i≤j≤7，使得以下之一必定成立：ai=aj=bi=bj，ai=aj=ci=cj，bi=bj=ci=cj．證：

顯然，每列中必有兩數字一致，共有種模式，有０或１兩種選擇．故共有·2

種選擇．·2=6．現有7列，．即必有２列在一致的兩行選擇一致的數字，即

有一矩形，四角的數字相等．3.6題（宗傳玉）

在邊長為1的正方形內任取5個點試證其中至少有兩點，其間距離小于證：

把１×１正方形分成四個(1/2)×(1/2)的正方形．如上圖.則這５點中必有兩點落在同一個小正方形內．而小正方形內的任兩點的距離都小于

．

3.7題（王星）

在邊長為1的等邊三角形內任取5個點試證其中至少有兩點，期間距離小于1/2．證：

把邊長為１的三角形分成四個邊長為1/2的三角形，如上圖：則這５點中必有兩點落在同一個小三角形中．小三角形中任意兩點間的距離都小于1/2．3.8題（王星）

任取11個整數，求證其中至少有兩個數它們的差是10的倍數。證：

整數的個位數的可能取值為０，１，…，９．共１０種可能．11個整數中必有２個數的個位數一致，即這兩個數之差能被１０整除．3.9題（王星）

把從1到326的326個整數任意分為5個部分，試證其中有一部分至少有一個數是某兩個數之和，或是另一個數的兩倍。證：

用反證法。設存在劃分P1∪P2∪P3∪P4∪P5＝[1，326]，Pi中沒有數是兩數之差．，則有一Pi中至少有66個數，A＝{a1,…,a66}，a1＜a2＜??＜a66，以下按書上174頁的例題證明可得．3.10題（王星）

A、B、C三種材料用作產品I、II、III的原料，但要求I阻止用B、C作原料，II不能用B

作原料，III不允許用A作原料，問有多少種安排方案？（假定每種材料只做一種產品的原料）解：

按題意可得如下的帶禁區的棋盤,其中有陰影的表示禁區．棋盤多項式為：R()=R()R()=(1+x)(1+3x+x2)=1+4x+4x2+x3

故方案數＝3!－4?2!+4?1!－1?0!＝13.11題（王星）

n個球放到m個盒子中去，n＜(m/2)(m－1)，試證其中必有兩個盒子有一致的球數。解：

設m個盒子的球的個數是a1,…,am，各不相等，且有0≤a1＜a2＜??＜am．則有a2≥1、am≥m－1，故

≥1+2+…+m－1＝(m/2)(m－1)，與n＜(m/2)(m－1)相矛盾！所以必有兩個盒子的球數相等．

3.12題（王星）

一年級有100名學生參與中文、英語和數學的考試，其中92人通過中文考試，75人通過英語考試，65人通過數學考試；其中65人通過中、英文考試，54人通過中文和數學考試，45人通過英語和數學考試，求通過3門學科考試的學生數。解：

設：通過中文考試的92人為集合A，通過英語考試的75人為集合B，通過數學考試的65人為集合C

則∣A∩B∣=65，∣A∩C∣=54，∣B∩C∣=45

由∣A∪B∪C∣=∣A∣+∣B∣+∣C∣-∣A∩B∣-∣A∩C∣-∣B∩C∣+∣A∩B∩C∣

故∣A∩B∩C∣=∣A∪B∪C∣-∣A∣-∣B∣-∣C∣+∣A∩B∣+∣A∩C∣+∣B∩C∣=100-92-75-65+65+54+45=32

通過3門學科考試的學生數為32。3.13題（王丹竹）試證(1)|(2)|A?B|?|B|?|A?B|

A?B?C|?|C|?|A?B|?|A?B?C|

證明：(1)

A?B??A?B??

A?B?B?A?BA?B?B?A?B=B

A=B

A?B?B?A?B=?

所以(2)

A?B?B?A?B成立

A?B?C?A?B?CA?B?A?B

=C?A?C?B?C?A?B?C

A?B?A?B?A?B

又由于由（a）得原式=C3.14題（王丹竹）

N?{1,2,?,1000}，求其中不被

?(A?B)?C?C?(A?C)?(B?C)

5和7除盡，但被3除盡的數的數目。

解：

設A3為被3除盡的集合

A為被5除盡的集合

5A為被7除盡的集合

7所以由題意得：A3?A5?A7

=??A3?A3?A5?A3?A5?A-應當少了一個吧？

7?1000??1000??1000??1000????????????3??3?5??3?7??3?5?7?

=333-66-47+9=2293.15題（王丹竹）

N?{1,2,?,120},求其中被

2，3，5，7中m個數除盡的數的數目，m=0，1，2，3，4。求不

超過120的素數的數目。素數？解：(1)m=0時不被2，3，5，7除盡的數為

A2?A3?A5?A=120-

7A

2???AAA33???AAA35?AAA77?AA52?A73?A22?A35?A52?A27+

AA5??????A-AA7?A?A?A?A3?A-

72573A5+A2?A3?A5?A7=120-（60+40+24+17）+

（20+12+8+8+8）-（4+2+1+1）=27

m=0時A2?A3??120??20?2?3???

A2?A5??120??12?2?5????120??8?2?7????120??5?3?7????120??3?5?7???

AAA2?AAA7?

?37?

?57?

?120??4?2?3?5???M=3時A2?A3?A5

?

AAA2?AAA?3AAA7??120??2?2?3?7???

2??57??120??1?2?5?7????120??1?3?5?7???

?3?57?

M=4時A2?A3?A5?A7(2)

由于112?120???0?2?3?5?7???

?121，故不超過120的合數必然是2，3，5，7的倍數

而且不超過120的合數的因子不可能超過11設Ai為不超過120的數的倍數集合，i=2，3，5，7

排除2，3，5，7這四個數又包含1這個非素數

2，3，5，7本身是素數，故所求不超過120的素數個數應當為27+4-1=30

3.16題（王丹竹）

求正整數n的數目，n除盡10，20中的至少一個數。這道題是這樣做嗎？解：

N為正整數

設A

10404030為被10除盡為被20除盡

3040A2030

A1040?n=???10??40??

A20A1030?n?=??30??20???

?????10??4030?20??n

40A2030

3.17題和3.18題（未完成）（王丹竹）

3.19題（孔令琪）{1000，1001，。。。，3000}，求其中是4的倍數但不是100的倍數的數目。此題下面的解法，我個人認為是不正確的。解：

設A，B分是4，100的倍數。

A??3000?1000??500??4???3000?1000??5??4*100??

A?B??

??A?B?A??A?B??500?5?450????3．20題（孔令琪）

在由a,a,a,b,b,b,c,c,c,組成的排列中，求滿足以下條件的排列數，（1）不存在相鄰3元素一致；解：

A，B，C分別表示aaa,bbb,ccc則：

A?B?C?7!?3!?2A?B?A?C?B?C?A?B?C?15!3!

S??9!?3!??3

?A?B?C?S?9!7!?A?3*?B?C5!3!???A?B?A?C?B?C??A?B?C??3!?3?3*?3!?2?1（2）相鄰兩元素不一致。這個怎么做？

3．21題（孔令琪）

求從O（0，0）點到（8，4）點的路徑數。已知（2，1）到（4，1）的線段，（3，1）到（3，2）的線段被封鎖解：

設A點坐標（2，1），B點坐標（4，1），C點坐標（3，1），D點坐標（3，2）令a為從O點到M點經過ACb為從O點到M點經過CBc為從O點到M點經過CD

s?c(12,4)?a?c(3,1)*c(8,3)?168b?c(4,1)*c(7,3)?140c?c(4,1)*c(7,2)?84a?b?105

a?c?63b?c?0a?b?c?0???a?b?c?s?(a?b?c)?(a?b?a?c?b?c)?a?b?c?2713．22題（孔令琪）

求滿足以下條件下面對于此題的解法正確，但是答案算錯了。x1+x2+x3=20,3?x1?9,0?x2?8,7?x3?17

解：令y1=x1-3,y2=x2,y3=x3-7

0?z1?6?y1,0?z2?8?y2,0?z3?17?y3,z1?z2?z3?6?y1?8?y2?17?y3

?31?(y1?y2?y3)?41?(x1?x2?x3)?21

則所求整數解的數目：c(23,21)=c(23,2)=2533．23題（孔令琪）

此題解法與上題一樣，所以不在求解，如有凝問請與我聯系！

3.24題（周英華）

求滿足以下條件的整數解數目：x1+x2+x3+x4=201≤x1≤5,0≤x2≤7,4≤x3≤8,2≤x4≤6解：

設y1=x1-1,y2=x2,y3=x3-4,y4=x4-2,

y1+y2+y3+y4=13

0≤y1≤4,0≤y2≤7,0≤y3≤4,0≤y4≤4,

若不附加上界條件的解根據公式應為

?13???134??1????1?6??16??????560?13??3?

對于有上界的問題要作變換

ε1=4-y1,ε2=7-y2,ε3=4-y3,ε4=4-y4,ε1≥0,ε2≥0,ε3≥0,ε4≥0,于是問題變為

ε1+ε2+ε3+ε4=6整數解的數目

?6?4???619??9???????????84??6??3?

3.25題（周英華）

證明滿足以下條件：x1+x2+……+xn=r

0≤xi≤k,i=1,2,……，n的整數解數目為

n?i?0?1)?i?n??r?(k(?1)????i??r?1i?n?1??解：

S,|S|=???n?r?1???r??

令S中具有x1≥k+1的子集A1，……，xi≥k+1的子集Ai,

問題轉化為求|A1∩A2∩…∩An||A1|=?r?n?k?2????r?1??r?n?2k?4???r?1??|A1∩A2|=

……

n|A1∩A2∩…∩An|=?i?0?n??r?(k?1)i?n?1?(?1)?????i??r?1?i

3.26題（周英華）

證明滿足以下條件：x1+x2+……+xn=r

1≤xi≤k,i=1,2,……，n的整數解數目為

n?i?0?n??r?ki?1?(?1)????

ir?1????i證明：

令yi=xi-1

則y1+y2+……+yn=r-n

0≤yi≤k,i=1,2,……，n

n由上題知?i?0n??r?(k?1)i?n?1?i?(?1)?????i??r?1?

代入得整數解數目為

n?i?0?n??r?ki?1?(?1)????

ir?1????i3.27題（周英華）

求n對夫妻排成一行，夫妻不相鄰的排列數。這道題可不可以用遞推關系試試？解：

(1)n個人排成一行方案數為n!N對夫妻排成一行方案數為n!2n

令Ai第i對夫妻相鄰而坐的集合，i=1,2,……，n(2)2n個人排成一行方案數為(2n)!

|Ai|相當于將第i對夫妻作為一個對象排列一行然后換位，故|A1|=2(2n-1)!

|A1∩A2|=22(2n-2)!……

|A1∩A2∩…∩An|=2nn!

故夫妻不相鄰排列數為N=(2n)!-2?n?n???1?(2n-1)!+22??n???2?(2n-2)!-……+(-1)n2nn!

=?h?0n?h?2???h?(2n-h)!

3.28題（周英華）未看。

設p,q∈N，p是奇數，現在有pq個珠子，著q種顏色，每種顏色有p個珠子。假定一致顏色的珠子無區別。試分別求滿足以下條件的珠子的排列數。

（1）同顏色的珠子在一起；

（2）同顏色的珠子處于不同的塊；（3）同顏色的珠子最多在兩個塊。解：

同顏色的珠子在一起的排列數p!

同顏色的珠子處于不同的塊的排列數p!qp

同顏色的珠子最多在兩個塊的排列數Ai相當于第i個某色球處于不同塊|A1|=q(pq)!

|A1∩A2|=q2(pq-1)!

……

|A1∩A2∩…∩Ap|=qp(pq-p)!N=q(pq)!-q2?p?p???1?(pq-1)!+……+(-1)pqp(qp-p)!

=?i?0pp?q??i??(pq?i)?3.29題（翟聰）

將r個一致的球放進n個有標志的盒子里，無一空盒，求方案數。解：

先拿出n個球在每個盒子里放一個球，再將剩下的r-n個球無限制地放入n個盒子中。根據定理1.3，r-n個球無限制地放到n個盒子中共有C(n+r-n-1,r-n)=C(r-1,r-n)=C(r-1,n-1)種放法。

3.30題（翟聰）未看。

n?1試證?i?0ni?(?1)???i?????n?r?i?1?????r??=???r?1????n?1?，r，n∈N，r>n

解：

設共有r-1個不同的紅球和n個不同的白球，從中取出n-1個球.

等式左邊每個累加項（不考慮符號）可化為：C(n,i)C(n+r-1-i,n-1-i)表示從這些球中取i個白球和n-1-i個紅球，表示至少取i個白球的組合數，即β(i)。

等式右邊表示只從r-1個紅球中取出n-1個球的組合數，表示恰好取0個白球的組合數，即α(0)。

根據廣義容斥定理α(0)=β(0)-β(1)+β(2)-…+(-1)n-1β(n-1)。原式證畢。3.31題（翟聰）設B是A的子集，

A=n，B=m，求A的子集包含B的子集的數目，設子集的元素數目為

r，m≤r≤n。（沒看懂，不會做）3.32題（翟聰）m,r,,n∈N,滿足證明：

從n個元素中取k個的組合，總含有制定的m個元素的組合數為??個元素為a1,a2,am,AK1?AK2?...?AKiAk?n?mm≤r≤n,試證???n?rm?i?=?(?1)??i?0?m???i?????n?i??????r?

?n?m??n?m??=??，設這????k?m??n?k?m

為不含ak的組合（子集），i=1，…,m.

mi?n?i??=???r???n?m???n?r??=??m?i?1?nAi=???r????m+?i?1(?1)i·

?(?1)i?j?1AKj(k1,k2,..ki)??(m,i)?r???k????3.33題（翟聰）此題我個人不知道D是什么玩意？求證a)D(n,r,k)證明：右邊=

???D(n?k,r?k,0)

rkr?k?(n?r)!1??rk(?1)i??r?ki?(n?k?i)!?(n?k?r?k0?r?k?0i?0(n?k?r?k)!?i?0(?1)i?r?k?0i?(n?0?i)!

r?k=?k?*

r?(n?r)!(?1)ir?ki?i)!=左邊

i?0

b)

D(n,r,k)

?1,k?1)=D(n?1,r+(n-1)D(n?1,r?1,k)+(r-1)(D(n?2,r?2,k)-D(n?2,r?2,k?1))

?(?1)?(n?r)!ii?0??rkr?kr?ki?(n?k?i)!??r?k?2i?(?1)?(n?r)!ii?0??r?1k?1r?kr?ki?(n?k?i)!?(n?1)*r?k?1??r?1kr?k?1(n?r)!?i?0(?1)i?r?k?1i?(n?k?i?1)!???r?2?r?k?2?ki(r?1)?(?1)?(n?r)!i?0??r?k?(n?k?i?2)!?r?kr?1k?1?r?2k?1?(n?r)!?i?0(?1)i?r?k?1i???(n?k?i?1)!???r?k?1r?1k???rki?0(?1)i?r?ki?(n?k?i)!??(?1)i??i?0(?1)i?r?ki?(n?k?i)!?(n?1)*?r?k??i?0(?1)??i?r?k?1i?(n?k?i?1)!??(r?1)???r?k?2r?2k??i?0?r?k?2i?(n?k?i?2)!??r?2k?1??i?0(?1)i?r?k?1i?(n?k?i?1)!?

r!(r?k)!k!(n?r)!r?k(r?1)!(r?1)!r?k?i?0(?1)i(r?k)!(r?k?i)!i!(n?k?i)!?(r?k)!(k?1)!(n?r)!?i?0(?1)i(r?k)!(r?k?i)!i!(r?2)!(n?k?i)!?(n?1)*(r?k?1)!k!(n?r)!r?k?1?i?0(?1)i(r?2)!???(r?k?2)!k!(r?1)?(n?r)!???r?k?r?k?2r?k?1?(r?k?2)!(r?k?1)!(r?k?1)!(k?1)!?ii(?1)(n?k?i?1)!??(?1)(r?k?i?2)!i!(n?k?i?2)!??(n?r)!(r?k?i?1)!i!i?0i?0???r?kr?(?1)i?0i(n?k?i)!(r?k?i)!i!?k?(?1)i?0i(n?k?i)!(r?k?i)!i!r?k?1?(n?1)?i?0(?1)i1(r?k?i?1)!i!?r?k?r?k?2(n?k?i?2)!(n?k?i?1)!?ii(?1)?k(?1)????(r?k?i?2)!i!(r?k?i?1)!i!i?0?i?0?

r?k(r?k)?(?1)i?0i(n?k?i)!(r?k?i)!i!r?k?1?(n?k?1)?i?0(?1)i(n?k?i?1)!(r?k?i?1)!i!r?k?2??i?0(?1)i(n?k?i?2)!(r?k?i?2)!i!r?k(r?k)?(?1)i?0i(n?k?i)!(r?k?i)!i!r?k?1?(n?k?1)?i?0(?1)i(n?k?i?1)!(r?k?i?1)!i!r?k?2??i?0(?1)i(n?k?i?2)!(r?k?i?2)!i!

c)

D(n,n,k)?n*D(n?1,n?1,k)?(?1)n!(n?k)!k!(?1)n?kn?kn?k??

nk?i?0(?1)i(n?k)!(n?k?i)!i!(n?k?i)!?n!(n?k?1)!k!n?k?1?i?0(?1)i(n?k?1)!(n?k?i?1)!i!(n?k?i?1)!?n!(n?k)!k!1i!n!k!n?k?1?k!

n!k!n!n?k(?1)i??i?0(?1)i1i!?(?1)n?kn!(n?k)!k!

i?0n?k?i?0(?1)i1i!?n!k!n?k?1?i?0(?1)i1i!?(?1)n?kn!(n?k)!k!

得證。d)

??D(n,r,k)???D(n?t,r?t,k?t)

krtt?(n?r)!????krtkr?k(?1)i?r?ki?(n?k?i)!????rtr?tk?t?r?ki?0(n?r)!?i?0(?1)i?r?ki?(n?k?i)!

k!r!(k?t)!t!(r?k)!k!(n?r)!r!(k?t)!t!(r?k)!(n?r)!r?kr?kr!(r?t)!?i?0(?1)i?r?ki?(n?k?i)!?(r?t)!t!(r?k)!(k?t)!(n?r)!r!r?k?i?0(?1)i?r?ki?(n?k?i)!

?i?0(?1)i?r?ki?(n?k?i)!?t!(r?k)!(k?t)!(n?r)!r?k?i?0(?1)i?r?ki?(n?k?i)!

反過程可證。

e)

D(n,r,k)?r*D(n?1,r?1,k)?D(n?1,r,k)

?(n?r)!r*?r?1k??rkr?k(?1)i?ir?ki?(n?k?i)!??(n?k?i?1)!??(n?r?1)!i?0r?k?1?(n?r)!?i?0(?1)?r?k?1i??rkr?k(?1)i?r?ki?(n?k?i?1)!i?0r!(r?k)!k!(n?r)!r*r?k?i?0(?1)i?r?ki?(n?k?i)!?r!(r?1)!(r?1?k)!k!(n?r)!r?k?1

r?k?i?0(?1)i?r?k?1i?(n?k?i?1)!?i?(n?r?1)!r?k(r?k)!k!(?1)i?r?ki?(n?k?i?1)!

i?0r?k?i?0(?1)i(n?k?i)!(r?k?i)!i!r?k?1??i?0(?1)(n?k?i?1)!(r?k?i?1)!i!?(n?r)?(?1)i?0i(n?k?i?1)!(r?k?i)!i!當i=0時，各項左右相等，對應當n=r-k-1時候，左右也相等。

剩余左右當i=r-k時候也相等，得證。F）

1r!r??i?0r!(r?i)!i!n?i(n?i)!?j?0(?1)j!jnn!?j?0(?1)j!j

3.34題（王卓）n?N,設Pn表示在{1，2，……，n}的全排列中，排除了k，緊隨以k+1，k=1，2……，k+1，

試證Pn=Dn+Dn-1,n?N.（不會做）

3.35題（王卓）

令Dn(k)=D(n,n,k),試證

(a)Dn(k)=???n??Dn-k??k?證明：

?n???k????n?kDn?k??D?n,n,k??(n?n)!i?i?0?n?k???n?k?i?!?(?1)???i??n?kii?n???k?n?k????1???i?0i?n?k?i???n?k?i?!???i?Dn?k?n?k?n?k??(?1)????0??i?0?n?k????n?k?i?!???i?????1?i?0?n?k?

???n?k?i?!???i??n???Dn?k?????Dn?k?k?(b)???n??n??n??D1???D2?????Dn?n!??????1??2??n?證明：

上面等式可變換為：

?n??n??n???D1???D2?????Dn?n!???????n?1??n?2??0?考慮n元素的集合S={1,2,…,n}，設T為S的排列全體，則|T|=n!。設Ai是S中恰有i個在其自然位置的n-排列全體，則

nAi?Aj??T??i?0Ai

n所以，|T|??i?0|Ai|

而，|?n??Ai|????Dn?i?i?n因此，n!??i?0?n???Dn?i???i?

(c)(k+1)Dn+1(k+1)=(n+1)Dn(k)證明：

?n?1??????k?1?0!n?1?k?1Dn?1?k?1???i?0?n?1?k?1???n?1?k?1?i?!?(?1)????i?ii?n?1?n?k?????1????k?1?i?0i?n?k????n?k?i?!???i??n?1?n?k??(?1)?k?1?Dn?1?k?1???k?1????k?1??i?0?n??n?1????k?n?k????1???i?0i?n?k????n?k?i?!??i??

?n?k????n?k?i?!??n?1?Dn?k???i??

3.36題（王卓）

令Dn(k)=D(n,n,k),試證

n(a)?k?0kDn(k)?n!

(b)Dn(0)-Dn(1)=(-1)n

n(c)?k?0n(k?1)D2n(k)?n!

(d)?k?0k(k?1)?(k?r?1)Dn(k)?n!

3.37題（王卓）試證

(a)??m,n????m???n?

(b)對于素數p1,i?1,?(pi)?p?pii?1

?1??1????pk???1??1??????1???根據n?p11p22?pkk則??n??n?1?????p1??p2??n?pi

??pi????n???1?1?i?ii?1??p?1???p?pn?1?????p?p???3.38題（王卓）

試證(a)???d??d/nn

??dd??n??n?d/n?根據反演定理可得n?

???d?d/n(b)??m,n???h????m???n?h,其中(c)n?N,n?3,??n?尋常是偶數m,n?N,h??m,n?

3.39題（王振華）3.40題（王振華）3.41題（王振華）（未完成）

3.42題（王振華）此題解答沒我沒怎么看懂。

一組人有1990個人，每個人至少有1327個朋友，試證其中四位，使得彼此都是好朋友解；

令外邊的都與括號里的1327個是朋友，1{1989}，從里邊不是外邊人朋友的找出2{1988}…..663{1327}再從里邊找人出來662，1{{1}，1236}直至663{{663}664}按上面的方法繼續663{{663}{663}1}把里邊的1拿出外邊一個進去為662，1{{1}{663}{663}}

這樣1與里邊的都是朋友，括號里前面括號的人與后邊的都是朋友，所以一定有四個人彼此是朋友。

3.43題（王振華）

在邊長為1的等邊三角形內任取5個點試證其中至少有兩點，期間距離小于1/2．證：

把邊長為１的三角形分成四個邊長為1/2的三角形，如上圖：則這５點中必有兩點落在同一個小三角形中．小三角形中任意兩點間的距離都小于1/2．3.44題（王居柱）

單位圓圓周上任意n?1個不同的點至少存在兩點其間距離不超過2sin這還用證明嗎？證明：

把圓周等分成ｎ段相等的弧，每段弧所對的最大弦長為Ｓ＝2sin?2?2。

，把ｎ＋１個點

放到這ｎ個圓弧上，根據鴿巢原理，必有兩個點在同一段弧上，這兩點的距離必小于等于2sin?2。

3.45題（王居柱）

邊長為1的正方形內任取9點，試證存在3個不同的點，由此構成的三角形面積不

過8。下面解法中為什么要放在8條邊上，可以放在其他地方嗎？有其他解法嗎？

證明：

把正方形等分為8個三角形，每個三角形的面積為8,產生以正方形中心的8條邊，把

9個點放到8條邊上，根據鴿巢原理，必有兩個點在同一條邊上，所以可以得到一個三角形的面積小于8。

3.46題（王居柱）

任給5個整數，試證其中必存在3個數的和被3除盡。

證明：

課本145頁例題，第（4）題

3.47題（王居柱）

A是n+1個數的集合，試證其中必存在兩個數，它們的差被n除盡。證明:

構造一個序列s1=a2-a1,s2=a3-a1,…….sn=an?1-a1,si?111sj（i?j）,

有兩種可能（1）若有一個sm(1?m?n)是n的倍數，則定理得證。（2）設在序列中沒有任何一個元素是n的倍數，則s1，s2………..sn除n的余數為1，2，3，……….n-1，由于有n個數，由鴿巢原理得，必有兩個

數的余數是一致的，不妨設si，sj的余數一致，

則si=ai?1-a1=bn+r…..(1)

sj=aj?1-a1=cn+r….(2)

兩式相減的

3.48題（王居柱）未看。

ai?1-aj?1=（b-c）n原式得證。

a2，A={a1，…………a2k?1}k?1,

aiai，是正整數，k=1,2,3,……2k+1,試證A的任意排列：

1ai，…………,ai恒有2k?12?（ai?aj）為偶數。

jj?12k?1證明：

根據鴿巢原理，a1，a2，…………a2k?1這2k+1個數中必有k+1個數同為偶數或同為

奇數，不妨設這k+1個數為a1，a2，…………ak?1，且同為奇數，則a1，

a2，…………a2k?1中至多有

k個偶數，根據鴿巢原理，

ai，ai，…………,ai12k?1中至少有一個是奇數，奇數和奇數之差為偶數，所以

ai?aj中必有一個是偶數，同理，有k+1個數同為偶數時也成立，j所以原式?（aij?aj）為偶數得證。

j?12k?1

3.49題（王健）

A是{1，2，……………,2n}中任意n+1個數,試證至少存在一對a,b?A,使下面結果成立：a

b

證明：

設所取n+1個數是a1,a2,………..an,an+1

對a1,a2,………..an,an+1序列中的每一個數去掉一切2的因子，直至剩下一個奇數為止。

結果得到由奇數組成的序列r1,r2,………..rn,rn+11到2n中只有n個奇數，故序列中至少有兩個是一致的。設ri=rj=r為，對應地有ai=2air,aj=2ajr,

若，則至少存在一對a,b?A,使下面結果成立：a3.50（王健）未完成

3.51（王健）未完成

b

3.52（王健）未完成

3.53（王健）未完成

3.54題（孫明柱）

二維空間的（x,y）點的坐標x和y都是整數的點稱為格點，任意5個格點的集合A，試證A中至少存在兩點，它們的中點也是格點。證明：

任意5個格點，對于x，y，5個整數中至少存在3個數為偶數或者為奇數它們的中點就是兩個點的對應數的和的一半，

1，當存在三個偶數時，則其中任意兩個數的和的一半能被2整除，余下的兩個奇數的和也能被2整除，即存在兩個格點。

2，當存在四或五個偶數時，則四個偶數中任意取兩個的數和是2的倍數，即存在兩個格點

反之存在奇數的狀況也一樣。

所以存在至少存在兩點，它們的中點也是格點。3.55題（孫明柱）令A為等差數列

1，4，7，10,…,100

中任選20個不同的數，試證其中至少存在兩個數，它們的和為104.證明：

在這34個數中，除去1和52，余下的4和100，7和97，…..49和55，它們的和為104，共16對，從A中任取20個數，除去1和52，從余下的16對數中取18個，根據鴿巢原理，其中至少存在一對數的和為104

3.56題（孫明柱）未看。

平面上6個點，不存在3點共一條直線，其中必存在3點構成一個三角形，有一內角小于30。

o證明：

首先任意選三個點構成一個三角形，把平面分成三角形內和三角形外兩部分，根據鴿巢原理，剩下的三個至少有兩個點在三角形內或三角形外，假設至少兩個點在三角形內，由于沒有三個點共線，

(1)當有兩個點在三角形內時，一個三角形至少存在一個內角是銳角，這兩點把三角形的這個銳角內角分成三等分，則至少有一個角是小于30，的，即存在

o一個內角小于30的三角形的

o(2)當有三個點在三角形內則，由(1)知，確定存在一個內角小于30的三角形的

o同理在三角形外也有同樣的結論。3.57題（孫明柱）這題沒意義。

n是大于等于3的整數，則以下數的集合：{2-1，22?1,2?1,???,23n?1?1}

中存在一數被n除盡。解：

我認為此題有爭議,當n=4時，數的集合是{2-1，2都不能被4除盡。

3.58題（孫明柱）這題待解，應當看。

n個人的集體，試證存在兩個人，在余下的n-2個人中，至少有二人認識，要么與這兩個人均不相識。

n22?1,2?1

3}即：{1，3，7}

-1個要么與

（未完成）

3.59題（李拂曉）3.60題（李拂曉）3.61題（李拂曉）

n各單位各派兩名代表去出席一會議。2n位代表圍一圓桌坐下。試問：（1）各單位代表并排坐著的方案是多少？

（2）各單位的兩人互不相鄰的方案數又是多少？此小問比較難，未看。解：

(1)方案數＝(n-1)!2n

(2)設第i個單位的代表相鄰的方案數為Ai,i=1,2,…,n

nnnk?i?1Ai????1?k?0??Ai????1?k?0kI??(n,k)i?I?n?k??(2n?2k?1)!2???k?

3.62題（李拂曉）此題有望考。一書架有m層，分別放置m類不同種類的書，每層n冊。先將書架上的圖書全部取出清理。清理過程要求不打亂所有的類別。試問:

（1）m類書全不在各自原來層次上的方案數有多少？（2）每層的n本書都不在原來位置上的方案數等于多少？

（3）m層書都不在原來層次，每層n本書也不在原來位置上的方案數又有多少？解：

3.63題（李拂曉）未看。

m+1行列的格子同m種顏色著色，每格著一種顏色，其中必有一個4角同色

的矩形。證：

每列有(m+1)行，只有m種顏色，故一列中必有兩格同色．同色的２個格子的行號有

種取法．有m種色，故有m種同色模式，現有m+1列，必有兩列

的同色模式一致．即由這兩列的對應行上有４個格子同色，正好是一個矩形的４個角上的格子．得證．

3.64題（高亮）未看。

兩名教師分別對6名學生同時進行兩門課程的面試（每名教師各管一門課程）每名學生

每門面試的時間都是半個小時，共有多少不同的面試順序？解

第一門課的順序有6!種；

其次門課的順序有：D6＝6!((1/2!)－(1/3!)＋(1/4!)－(1/5!)＋(1/6!))＝265;故總順序有6!×265種．3.65題（高亮）未完成

3.66題（高亮）未完成

3.67題（高亮）未完成

3.68題（高亮）未完成

3.69題（頓紹坤）

試證(mn)!被(m!)m整除。證明：

：我認為此題確定缺少已知的某個或幾個條件。例如，當m=2，n=1時，(mn)!=2!=2