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

第三章習(xí)題 3 1某甲參加一種會(huì)議 會(huì)上有6位朋友 某甲和其中每人在會(huì)上各相遇12次 每二人各相遇6次 每三人各相遇4次 每四人各相遇3次 每五人各相遇2次 每六人各相遇一次 1人也沒(méi)有遇見(jiàn)的有5次 問(wèn)某甲共參加了幾次會(huì)議 1 解設(shè)Ai為甲與第i個(gè)朋友相遇的會(huì)議集 i 1 6 則 共33次會(huì)議 2 求從1到500的整數(shù)中被3和5整除但不被7整除的數(shù)的個(gè)數(shù) 解設(shè)A3 被3整除的數(shù)的集合A5 被5整除的數(shù)的集合A7 被7整除的數(shù)的集合 3 n代表參加會(huì)議 試證其中至少有2人各自的朋友數(shù)相等 解 每個(gè)人的朋友數(shù)只能取0 1 n 1 以下分兩種情況討論 若有人的朋友數(shù)為0 即此人和其他人都不認(rèn)識(shí) 則其他n 1個(gè)人的最大取數(shù)不超過(guò)n 2 必有兩人認(rèn)識(shí)人數(shù)相等 若沒(méi)有人的朋友數(shù)為0 則這n個(gè)人的朋友數(shù)的實(shí)際取數(shù)只有n 1種可能 所以至少有 人的朋友數(shù)相等 3 4試給下列等式以組合意義 a 從n個(gè)元素中取k個(gè)元素的組合 總含m個(gè)指定的元素的組合數(shù)為C n m k m 設(shè)這m個(gè)元素為a1 a2 am Ai為不含ai的組合 i 1 2 m b 令k n m l個(gè)相同的球放入k個(gè)不同的盒子里 每盒不空的方案數(shù)為C n m l n m 1 l n m C l 1 n m 1 設(shè)Ai為第i個(gè)盒子為空的方案集 i 1 2 k l個(gè)相同的球放入n個(gè)不同的盒子里 指定的m個(gè)盒子為空 其他盒子不空的方案數(shù)為C l 1 n m 1 c 設(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ù)a1a2a3a4a5a6a7 b1b2b3b4b5b6b7 c1c2c3c4c5c6c7 試證存在整數(shù)i和j 1 i j 7 使得下列之一必然成立 ai aj bi bj ai aj ci cj bi bj ci cj 證明 顯然 每列中必有兩數(shù)字相同 共有C 3 2 種模式 有 或 兩種選擇 故共有C 3 2 2種選擇 C 3 2 2 6 現(xiàn)有7列 即必有 列在相同的兩行選擇相同的數(shù)字 即有一矩形 四角的數(shù)字相等 3 6在邊長(zhǎng)為1的正方形內(nèi)任取5點(diǎn) 試證其中至少有兩點(diǎn) 其間距離小于 證把 正方形分成四個(gè)相等的小正方形 如下圖 則這 點(diǎn)中必有兩點(diǎn)落在同一個(gè)小正方形內(nèi) 而小正方形內(nèi)的任兩點(diǎn)的距離都小于 證把邊長(zhǎng)為 的三角形分成四個(gè)邊長(zhǎng)為 的三角形 如下圖 則這 點(diǎn)中必有兩點(diǎn)落在同一個(gè)小三角形中 3 7在邊長(zhǎng)為1的等邊三角形內(nèi)任取5點(diǎn) 試證至少有兩點(diǎn)距離小于1 2 3 8任取11個(gè)數(shù) 求證其中至少有兩個(gè)數(shù)它們的差是10的倍數(shù) 證明 一個(gè)數(shù)是不是10的倍數(shù)取決于這個(gè)數(shù)的個(gè)位數(shù)是不是0 是0就是10的倍數(shù) 一個(gè)數(shù)的個(gè)位數(shù)只可能是0 1 9十個(gè)數(shù) 任取11個(gè)數(shù) 其中必有兩個(gè)個(gè)位數(shù)相同 那么這兩個(gè)數(shù)的差的個(gè)位數(shù)必然是0 3 9把從1到326的326個(gè)整數(shù)任意分為5個(gè)部分 試證其中有一部分至少有一個(gè)數(shù)是某兩個(gè)數(shù)之和 或是另一個(gè)數(shù)的兩倍 證明 用反證法 設(shè)存在劃分 設(shè)這66個(gè)元素為a1 a2 a3 a66 構(gòu)造b1 a2 a1 b2 a3 a1 b65 a66 a1 令B b1 b2 b65 這65個(gè)元素屬于1到326 如果這65個(gè)元素有任何一個(gè)屬于P1 則定理得證 否則 2 因?yàn)?因此至少有一個(gè)集合含至少B中17個(gè)元素 設(shè)這個(gè)集合為p2 設(shè)這6個(gè)元素為 構(gòu)造 設(shè)C c1 c2 c16 否則 3 因?yàn)?因此至少有一個(gè)集合含至少C中6個(gè)元素 設(shè)這個(gè)集合為p3 設(shè)這11個(gè)元素為 構(gòu)造 如果 則定理得證 同樣可證明d1和d2既可表示成p1中元素之差 也可表示成p2p3中元素之差 設(shè)D d1 d2 d5 否則 3 因?yàn)?因此至少有一個(gè)集合含至少D中3個(gè)元素 設(shè)這個(gè)集合為p4 設(shè)這3個(gè)元素為 構(gòu)造 如果 則定理得證 同樣可證明ei既可表示成p1中元素之差 也可表示成p2p3p4中元素之差 否則 同樣可證明e2 e1既可表示成p1中數(shù)之差 也可表示成p2p3p4中數(shù)之差 e2 e1是1到326中的數(shù) 設(shè)f d2 d1 因此 1到326的326個(gè)整數(shù)任意分成5部分 其中必有一部分其中有一個(gè)數(shù)是另兩個(gè)數(shù)之差 設(shè)ai aj ah 那么反過(guò)來(lái) aj ai ah 構(gòu)造 3 10A B C三種材料用作產(chǎn)品I II III的原料 但要求I禁止用B和C作原料 II不能用B作原料 III不允許用A作原料 問(wèn)有多少種安排方案 解按題意可得如下的帶禁區(qū)的棋盤其中有陰影的表示禁區(qū) ABC 禁區(qū)的棋子多項(xiàng)式為 R R R 1 x 1 3x x2 1 4x 4x2 x3 故方案數(shù) 3 4 2 4 1 1 0 1 3 11 n個(gè)球放到m個(gè)盒子中去 n m m 1 2 試證其中必有兩個(gè)盒子有相同的球數(shù) 證明 用反證法 假如沒(méi)有兩個(gè)盒子的球數(shù)相同 那么m個(gè)盒子中最少需要0 1 2 m 1 共m m 1 2 因此必有兩個(gè)盒子有相同的球數(shù) 3 12 一年級(jí)有100名學(xué)生參加中文 英文和數(shù)學(xué)的考試 其中92人通過(guò)中文考試 75人通過(guò)英語(yǔ)考試 65人通過(guò)數(shù)學(xué)考試 其中65人通過(guò)中英文考試 54人通過(guò)中文和數(shù)學(xué)考試 45人通過(guò)英語(yǔ)和數(shù)學(xué)考試 求通過(guò)三門學(xué)科考試的學(xué)生數(shù) 3 13 試證 證明 a 3 15 N 1 2 120 求其中被2 3 5 7 m個(gè)數(shù)除盡的數(shù)的數(shù)目 m 0 1 2 3 4 求不超過(guò)120的素?cái)?shù)的數(shù)目 解設(shè)A2 被2整除的數(shù)的集合A3 被3整除的數(shù)的集合A5 被5整除的數(shù)的集合A7 被7整除的數(shù)的集合 素?cái)?shù)為27 1 4 30 3 16 求正整數(shù)n的數(shù)目 n除盡1040 2030中至少一個(gè)數(shù) 解 設(shè)A1為能除盡1040的數(shù) A2為能除盡2030的數(shù) 3 17 求正整數(shù)n的數(shù)目 n除盡1060 2050 3040至少一個(gè)數(shù) 解 3 18 求下列集合中不是n2 n3 形式的數(shù)的數(shù)目 解 3 19 求下列集合中是4的倍數(shù) 但不是100的倍數(shù)的數(shù)的數(shù)目 3 20 在由a a a b b b c c c組成的排列中 求滿足下列條件的排列數(shù) a 不存在相鄰三元素相同 b 相鄰兩元素不相同 解a 設(shè)A1為至少存在三元素aaa相鄰的排列集 A2為至少存在三元素bbb相鄰的排列集 A3為至少存在三元素ccc相鄰的排列集 解b 設(shè)A1為至少存在二元素aa相鄰的排列集 A2為至少存在二元素bb相鄰的排列集 A3為至少存在二元素cc相鄰的排列集 3 21 求從O 0 0 點(diǎn)到 8 4 點(diǎn)的路徑數(shù) 已知 2 1 到 4 1 的線路 3 1 到 3 2 的線路被封鎖 解 設(shè)過(guò) 2 1 到 4 1 的線路的路徑數(shù)是A1過(guò) 3 1 到 3 2 的線路的路徑數(shù)是A2 3 22 求滿足條件x1 x2 x3 20 3 x1 9 0 x2 8 7 x3 17 的整數(shù)解數(shù)目 解 設(shè)A1是滿足x1 3的解 A2是滿足x1 10的解 A3是滿足x2 9的解 A4是滿足x3 7的解 A5是滿足x3 18的解 A1的解等價(jià)于 x1 4 x2 x3 20 其解的數(shù)目為C 3 16 1 16 A2的解等價(jià)于 x1 10 x2 x3 20 其解的數(shù)目為C 3 10 1 10 A3的解等價(jià)于x1 x2 9 x3 20 其解的數(shù)目為C 3 11 1 11 A4的解等價(jià)于x1 x2 x3 7 20 其解的數(shù)目為C 3 13 1 13 A5的解等價(jià)于x1 x2 x3 18 20 其解的數(shù)目為C 3 2 1 2 A1交A4的解等價(jià)于 x1 4 x2 x3 7 20 其解的數(shù)目為C 3 9 1 9 A1交A4交A2的解等價(jià)于 x1 10 x2 x3 7 20 其解的數(shù)目為C 3 3 1 3 A1交A4交A3的解等價(jià)于 x1 3 x2 9 x3 7 20 其解的數(shù)目為C 3 1 1 1 A1交A4交A5的解等價(jià)于 x1 3 x2 x3 18 20 其解的數(shù)目為0 A1交A4交A2交A3的解等價(jià)于 x1 10 x2 9 x3 7 20 其解的數(shù)目為0 A1交A4交A2交A5的解等價(jià)于 x1 10 x2 x3 18 20 其解的數(shù)目為0 A1交A4交A3交A5的解等價(jià)于 x1 3 x2 9 x3 18 20 其解的數(shù)目為0 A1交A4交A2交A3交A5的解等價(jià)于 x1 10 x2 9 x3 18 20 其解的數(shù)目為0 3 25 試證滿足下列條件x1 xn r 0 xi k的整數(shù)解數(shù)目為 設(shè)Ai是滿足xi k 1的整數(shù)解集合 3 26 試證滿足下列條件x1 xn r 1 xi k的整數(shù)解數(shù)目為 設(shè)Ai是滿足xi k 1的整數(shù)解集合 3 27 求n對(duì)夫妻排成一行 夫妻不相鄰的排列數(shù) 設(shè)Ai是第i對(duì)夫妻排在一起的排列集 3 28 p q N p是奇數(shù) 現(xiàn)有pq個(gè)珠子 著q種顏色 每種顏色有p個(gè)珠子 假定相同顏色的珠子無(wú)區(qū)別 試分別求滿足以下條件的珠子的排列數(shù) a 同顏色的珠子在一起 b 同顏色的珠子處于不同的塊 c 同顏色的珠子最多在兩個(gè)塊 解a 解b 3 29 將r個(gè)相同的球放進(jìn)n個(gè)有標(biāo)志的盒子 無(wú)一空盒 求方案數(shù) 解 兩種算法 1 解2 設(shè)Ai為第i盒為空 其它盒任意的方案數(shù) 3 30 由28題 兩種算法應(yīng)相等 3 31 設(shè)B是A的子集 求A的子集包含B的子集的數(shù)目 設(shè)子集的元素?cái)?shù)目為r m r n 解 設(shè)B中元素為a1 a2 am 設(shè)A1是不包含a1的A的r個(gè)元素的子集數(shù)目 A2是不包含a2的A的r個(gè)元素的子集數(shù)目 Am是不包含am的A的r個(gè)元素的子集數(shù)目 另外一種算法 先從A中取出B的m個(gè)元素 然后在從剩余的n m個(gè)元素中取出r m 共C n m r m C n m n r 3 32 綜合3 31兩種情況可得3 32 3 44 單位圓周上任意n 1個(gè)不相同的點(diǎn)至少存在兩點(diǎn) 其間距離不超過(guò) 把圓周分成n等分 每份中的距離不超過(guò) 3 45 邊長(zhǎng)為1的正方形內(nèi)任取9點(diǎn) 試證存在3個(gè)不同的點(diǎn) 由此構(gòu)成的三角形面積不超過(guò)1 8 解 將邊長(zhǎng)為1的正方形等分成四部分 由鴿鴿巢原理 必有三點(diǎn)落在一個(gè)小正方形內(nèi) 這三點(diǎn)形成的三角形的面積不超過(guò)1 8 3 47 A是n 1個(gè)數(shù)的集合 試證其中必存在兩個(gè)數(shù) 它們的差被n除盡 解 n 1個(gè)數(shù)除以n的余數(shù)為0 1 2 n 1 若有兩個(gè)以上余數(shù)為零 那么這兩個(gè)數(shù)就是答案 否則 至少有n個(gè)數(shù)的余數(shù)非零 根據(jù)鴿巢原理 必有兩個(gè)余數(shù)相同 這兩個(gè)數(shù)便是答案 3 48 A a1 a2 a2k 1 k 1 ai是正整數(shù) k 1 2 2k 1 試證A的任意排列 恒有 為偶數(shù) 證明 A有2k 1個(gè)數(shù) 因此A中必有不少于k 1個(gè)奇數(shù)或不少于k 1個(gè)偶數(shù) 證明 設(shè)A有k 1個(gè)奇數(shù) 那么 也有k 1個(gè)奇數(shù) 共有2k 1組 其中有2k 2個(gè)奇數(shù) 因此必有兩個(gè)奇數(shù)在一組 有k 1個(gè)偶數(shù)時(shí)情況相同 3 49 A是 1 2 2n 中任意n 1個(gè)數(shù) 試證至少存在一對(duì)a b A使下面結(jié)果成立 a b 書(shū)中例題 3 50 A是 1 2 2n 中任意n 1個(gè)數(shù) 試證至少存在一對(duì)a b A使得a與b互素 從A中任意取n 1個(gè)數(shù) 必有兩個(gè)數(shù)相鄰 相鄰數(shù)互素 3 51 A是由13個(gè)互不相等的實(shí)數(shù)組成的集合 則至少存在一對(duì)x y屬于A 使 3 55 令A(yù)為從等差數(shù)列1 4 7 10 100中任選20個(gè)不同的數(shù) 試證其中至少存在兩個(gè)數(shù) 它們的和為104 項(xiàng)數(shù)是1 100 1 3 34 去掉1和52 共32個(gè)項(xiàng) 任取20個(gè)不同的數(shù) 至少有18個(gè)是32項(xiàng)中的數(shù) 4 100 7 97 因此至少有兩個(gè)數(shù)落在同一組中 也就是存在兩個(gè)數(shù)它們的和為104 3 56 平面上6個(gè)點(diǎn) 不存在3點(diǎn)共一條直線 其中必存在3點(diǎn)構(gòu)成一個(gè)三角形 有一內(nèi)角小于等于30度 平面上6個(gè)點(diǎn)構(gòu)成一個(gè)6邊形 其內(nèi)角和為720度 必有一角不大于120度 從這個(gè)角出發(fā)到各頂點(diǎn)的連線構(gòu)成4個(gè)角 這4個(gè)角度數(shù)之和是120度 因此至少有一個(gè)角的度數(shù)不大于30度 3 57 n是大于等于3的整數(shù) 則下列數(shù)的集合 2 1 22 1 23 1 2n 1 1 中存在一數(shù)被n除盡 首先這是n 1個(gè)奇數(shù) 假如n是偶數(shù)時(shí) 不可能 當(dāng)n 4時(shí) 數(shù)列為 1 3 7 不可能被n除盡 題 3 61 n個(gè)單位各派兩名代表出席一個(gè)會(huì)議 2n位代表圍一圓桌坐下問(wèn) a 各單位代表并排坐著的方案有多少 b 各單位的兩人互不相鄰的方案數(shù)又等于多少 b 各單位的兩人互不相鄰的方案數(shù)又等于多少 設(shè)第i個(gè)單位相鄰的方案數(shù)為Ai 3 62 一書(shū)架有m層 分別放置m類不同種類的書(shū) 每層n冊(cè) 現(xiàn)將書(shū)架上的圖書(shū)全部取出清理 清理過(guò)程要求不打亂所在的類別 試問(wèn) a m類書(shū)全不在各自原來(lái)層次上的方案數(shù)有多少 b 每層的n本書(shū)都不在原來(lái)位置上的方案數(shù)等于多少 c m層書(shū)都不在原來(lái)層次 每層n本書(shū)也不在原來(lái)位置上的方案數(shù)又是多少 3 64兩名教師分別對(duì)6名學(xué)生進(jìn)行面試 每位教師各負(fù)責(zé)一門課 每名學(xué)生面試時(shí)間固定 試問(wèn)共有多少種面試的順序 解第一門課的順序有6 種第二門課的順序有 共有6 265 3 65X 0 1 2 9 10 從X中任取7個(gè)元素 則其中必有兩個(gè)元素之和等于10 分成6組 0 10 1 9 4 6 5 從中任取7個(gè)數(shù) 除去5 還剩6個(gè)數(shù) 按鴿巢原理 必有兩個(gè)數(shù)落在一組中 而每組兩個(gè)數(shù)之和都是10 3 66每邊長(zhǎng)為3的等邊三角形內(nèi)取10個(gè)點(diǎn) 試證至少有一對(duì)點(diǎn)距離小于1 如果把三角形分成9個(gè)邊長(zhǎng)為1的等邊三角形 10個(gè)點(diǎn)必有至少兩個(gè)點(diǎn)落在1個(gè)小三角形上 其距離必小于1 3 67任取7個(gè)不同的正整數(shù) 其中至少存在兩個(gè)整數(shù)a和b使得a