組合數(shù)學(xué)課后答案

1、作業(yè)習(xí)題答案作業(yè)習(xí)題答案習(xí)題二習(xí)題二2.1證明：在一個(gè)至少有證明：在一個(gè)至少有2人的小組中，總存在兩個(gè)人，他們?cè)诮M內(nèi)所認(rèn)識(shí)的人數(shù)相同。人的小組中，總存在兩個(gè)人，他們?cè)诮M內(nèi)所認(rèn)識(shí)的人數(shù)相同。證明：證明：假設(shè)沒(méi)有人誰(shuí)都不認(rèn)識(shí)：那么每個(gè)人認(rèn)識(shí)的人數(shù)都為假設(shè)沒(méi)有人誰(shuí)都不認(rèn)識(shí)：那么每個(gè)人認(rèn)識(shí)的人數(shù)都為[1n1]，由鴿巢原理知，，由鴿巢原理知，n個(gè)人個(gè)人認(rèn)識(shí)的人數(shù)有認(rèn)識(shí)的人數(shù)有n1種，那么至少有種，那么至少有2個(gè)人認(rèn)識(shí)的人數(shù)相同。個(gè)人認(rèn)識(shí)的人數(shù)相同

2、。假設(shè)有假設(shè)有1人誰(shuí)都不認(rèn)識(shí)：那么其他人誰(shuí)都不認(rèn)識(shí)：那么其他n1人認(rèn)識(shí)的人數(shù)都為人認(rèn)識(shí)的人數(shù)都為[1n2]，由鴿巢原理知，，由鴿巢原理知，n1個(gè)人認(rèn)識(shí)的人數(shù)有個(gè)人認(rèn)識(shí)的人數(shù)有n2種，那么至少有種，那么至少有2個(gè)人認(rèn)識(shí)的人數(shù)相同。個(gè)人認(rèn)識(shí)的人數(shù)相同。2.3證明：平面上任取證明：平面上任取5個(gè)坐標(biāo)為整數(shù)的點(diǎn)，則其中至少有兩個(gè)點(diǎn)，由它們所連線段的中點(diǎn)個(gè)坐標(biāo)為整數(shù)的點(diǎn)，則其中至少有兩個(gè)點(diǎn)，由它們所連線段的中點(diǎn)的坐標(biāo)也是整數(shù)。的坐標(biāo)也是整數(shù)。證明

3、：證明：方法一：方法一：有5個(gè)坐標(biāo)，每個(gè)坐標(biāo)只有個(gè)坐標(biāo)，每個(gè)坐標(biāo)只有4種可能的情況：（奇數(shù)，偶數(shù)）種可能的情況：（奇數(shù)，偶數(shù)）；（奇數(shù)，奇數(shù)）；（奇數(shù)，奇數(shù)）；（偶數(shù)，；（偶數(shù)，偶數(shù)）偶數(shù)）；（偶數(shù)，奇數(shù)）；（偶數(shù)，奇數(shù)）。由鴿巢原理知，至少有。由鴿巢原理知，至少有2個(gè)坐標(biāo)的情況相同。又要想使中點(diǎn)的坐個(gè)坐標(biāo)的情況相同。又要想使中點(diǎn)的坐標(biāo)也是整數(shù)，則其兩點(diǎn)連線的坐標(biāo)之和為偶數(shù)。因?yàn)闃?biāo)也是整數(shù)，則其兩點(diǎn)連線的坐標(biāo)之和為偶數(shù)。因?yàn)槠鏀?shù)奇數(shù)奇數(shù)

4、奇數(shù)=偶數(shù)偶數(shù)；偶數(shù)偶數(shù)偶數(shù)偶數(shù)=偶數(shù)。因此只需找以上偶數(shù)。因此只需找以上2個(gè)情況相同的點(diǎn)。而已證明：存在至少個(gè)情況相同的點(diǎn)。而已證明：存在至少2個(gè)坐標(biāo)的情況相同。證個(gè)坐標(biāo)的情況相同。證明成立。明成立。方法二：方法二：對(duì)于平面上的任意整數(shù)坐標(biāo)的點(diǎn)而言，其坐標(biāo)值對(duì)對(duì)于平面上的任意整數(shù)坐標(biāo)的點(diǎn)而言，其坐標(biāo)值對(duì)2取模后的可能取值只有取模后的可能取值只有4種情況，種情況，即：即：(00)(01)(10)(11)，根據(jù)鴿巢原理，根據(jù)鴿巢原理5個(gè)點(diǎn)

5、中必有個(gè)點(diǎn)中必有2個(gè)點(diǎn)的坐標(biāo)對(duì)個(gè)點(diǎn)的坐標(biāo)對(duì)2取模后是相同類(lèi)取模后是相同類(lèi)型的，那么這兩點(diǎn)的連線中點(diǎn)也必為整數(shù)。型的，那么這兩點(diǎn)的連線中點(diǎn)也必為整數(shù)。2.4一次選秀活動(dòng)，每個(gè)人表演后可能得到的結(jié)果分別為“通過(guò)”一次選秀活動(dòng)，每個(gè)人表演后可能得到的結(jié)果分別為“通過(guò)”、“淘汰”和“待定”“淘汰”和“待定”，至，至少有多少人參加才能保證必有少有多少人參加才能保證必有100個(gè)人得到相同的結(jié)果？個(gè)人得到相同的結(jié)果？證明：證明：根據(jù)推論根據(jù)推論2.2

6、.1，若將，若將3（1001）1=298個(gè)人得到個(gè)人得到3種結(jié)果，必有種結(jié)果，必有100人得到相同結(jié)人得到相同結(jié)果。果。2.9將一個(gè)矩形分成將一個(gè)矩形分成(m1)行列的網(wǎng)格每個(gè)格子涂列的網(wǎng)格每個(gè)格子涂1種顏色，有種顏色，有m種顏色可以種顏色可以112mm????????選擇，證明：無(wú)論怎么涂色，其中必有一個(gè)由格子構(gòu)成的矩形的選擇，證明：無(wú)論怎么涂色，其中必有一個(gè)由格子構(gòu)成的矩形的4個(gè)角上的格子被涂上同個(gè)角上的格子被涂上同一種顏色。一種顏

7、色。證明：證明：（1）對(duì)每一列而言，有（）對(duì)每一列而言，有（m1）行，）行，m種顏色，有鴿巢原理，則必有兩個(gè)單元格顏色相種顏色，有鴿巢原理，則必有兩個(gè)單元格顏色相同。同。（2）每列中兩個(gè)單元格的不同位置組合有）每列中兩個(gè)單元格的不同位置組合有種，這樣一列中兩個(gè)同色單元格的位種，這樣一列中兩個(gè)同色單元格的位12m???????解：解：n=20，r=4，1204117238044nrr?????????????????????????3.1

8、7一局乒乓球比賽中，運(yùn)動(dòng)員甲以一局乒乓球比賽中，運(yùn)動(dòng)員甲以11:7戰(zhàn)勝運(yùn)動(dòng)員乙，若在比賽過(guò)程中甲從來(lái)沒(méi)有落后戰(zhàn)勝運(yùn)動(dòng)員乙，若在比賽過(guò)程中甲從來(lái)沒(méi)有落后過(guò)，求有多少種可能的比分記錄？過(guò)，求有多少種可能的比分記錄？解：根據(jù)題意，相當(dāng)于求從點(diǎn)解：根據(jù)題意，相當(dāng)于求從點(diǎn)(00)到點(diǎn)到點(diǎn)(117)且從下方不穿過(guò)且從下方不穿過(guò)y=x的非降路徑數(shù)，即為：的非降路徑數(shù)，即為：11711171(117)!(1171)132601012(111)!7!??

9、????????????????????3.211)會(huì)議室中有會(huì)議室中有2n1個(gè)座位，現(xiàn)擺成個(gè)座位，現(xiàn)擺成3排，要求任意兩排的座位都占大多數(shù)，求有多少排，要求任意兩排的座位都占大多數(shù)，求有多少種擺法？種擺法？解：解：(1)方法方法1：如果沒(méi)有附加限制則相當(dāng)于把如果沒(méi)有附加限制則相當(dāng)于把2n1個(gè)相同的小球放到個(gè)相同的小球放到3個(gè)不同的盒子里，有個(gè)不同的盒子里，有種方案，而不符合題意的擺法是有一排至少有種方案，而不符合題意的擺法是有一排至少

10、有n1個(gè)座位。這個(gè)座位。這213123312nn?????????????????相當(dāng)于將相當(dāng)于將n1個(gè)座位先放到個(gè)座位先放到3排中的某一排，再將剩下的排中的某一排，再將剩下的2n1(n1)=n個(gè)座位任意分到個(gè)座位任意分到3排中，這樣的擺法共有排中，這樣的擺法共有種方案，所以符合題意的種方案，所以符合題意的21(1)3123322nnn?????????????????????擺法有：擺法有：23213222nnn???????????

11、?????????????方法方法2：設(shè)第一排座位有：設(shè)第一排座位有x1個(gè)，第二排座位有個(gè)，第二排座位有x2個(gè)，第三排座位有個(gè)，第三排座位有x3個(gè)。個(gè)。x1x2x3=2n1，且，且x1x2≥(2n1)2，x1x3≥(2n1)2，x2x3≥(2n1)2，即，即x1x2≥n1，x1x3≥n1，x2x3≥n1，令，令y1=x1x2n1，y2=x1x3n1，y3=x2x3n1，可知，可知y1y2y3=2(2n1)3(n1)=n1且yi≥0，1≤

12、i≤3。顯然，。顯然，x方程滿足要求的解與方程滿足要求的解與y方程非負(fù)整方程非負(fù)整數(shù)解一一對(duì)應(yīng)，有數(shù)解一一對(duì)應(yīng)，有種。種。1311312nn??????????????????方法方法3：要求每行非空：要求每行非空如果沒(méi)有附加限制則相當(dāng)于把如果沒(méi)有附加限制則相當(dāng)于把2n1個(gè)相同的小球放到個(gè)相同的小球放到3個(gè)不同的盒子里，不允許為個(gè)不同的盒子里，不允許為空，有空，有種方案，而不符合題意的擺法是有一排至少有種方案，而不符合題意的擺法是有一排