數學 2 Chapter 2 2-1 集合與計數原理 學習目標 : 首先能理解基本的邏輯用語中, 或 且 與 敘述的否定 的意義,以及 笛摩根定律,以便處理 集合 與 集合的計數 相關的問題.再者,能了解 聯集 交集 補集 差集 積集 與 文氏圖 的意義,以及集合之間的運算法則,並結合基本的計數原理,包括 : 窮舉法 加法原理 乘法原理 取捨原理,來處理生活中常見的計數問題. 甲 基本的邏輯用語 在本章中, 我們的學習重點在於如何有效地處理計數問題, 也就是第 2 節中的排列組合問題 在此之前我們將先介紹一些在處理計數問題時所用到的用語與概念, 但同學們或許會覺得有一點抽象, 這等到學到了第 2 節, 我們會讓你知道在這節中所介紹的抽象概念, 如何在處理實際問題時使用. 所以請先耐心學好這節的內容. 1. 何謂敘述? 在數學的語言中, 能判斷其對或錯的語句, 稱為敘述. ( 或命題 ) 例 :(1) 三角形的三個內角和為 180. (2) 正三角形都是等腰三角形. (3) 長方形都是正方形. 2. 與敘述 p 意思相反 的敘述, 稱為 p 的 否定敘述否定敘述. ( 或否定命題 ) 例 :(1) 若敘述 p 為 n 是偶數, 則 p 的 否定敘述 為 n 不是偶數. (2) 若敘述 q 為 n 3, 則 q 的 否定敘述 為 n< 3. 註 : 通常 p 的 否定敘述 會用符號 ~p 或 p 來表示. 3. 在數學中, 我們經常用使用 或 且 來連接兩個敘述, 成為一個新的敘述. 例 :(1) 2 是偶數且 3 是奇數 (2) a= 0 或 b= 0 (3) n 是 2 的倍數且 n 是 3 的倍數 (4) x> 1且 x< 2 註 : 有些書本使用符號 來代表 或, 而用符號 來代表 且. 複合敘述 ( 或 且 ) 例 1: 設正整數 n 10,已知 n 是 2 的倍數或 n 是 3 的倍數,試舉出所有可能的 n. 例 2: 設正整數 n 25,已知 n 除以 4 餘 1 且 n 是質數,試舉出所有可能的 n. 隨堂練習 : 設 n 是正整數,已知 n 是 8 的因數或 n 是 12 的因數,試舉出所有可能的 n. 隨堂練習 : 設正整數 n 50,已知 n 是平方數且 n 的個位數字為 6,試舉出所有可能的 n. 1
4. 如果使用 或 且 來連接兩個敘述, 成為一個新的敘述, 那這個新的敘述的 否定敘述 為? 例 : 敘述 p 代表 n 是 2 的倍數, 敘述 q 代表 n 是 3 的倍數, 那麼 (1) p q 代表 (2) p q 代表 (3) p q 的 否定敘述 為 (4) p q 的 否定敘述 為 例 : 設正整數 n 10,已知 n 不是 2 的倍數且 n 不是 3 的倍數,試舉出所有可能的 n. 例 : 若敘述 p 為 a= 0 或 b= 0, 則 p 的 否定敘述 為. 例 : 若敘述 p 為 x> 1且 x< 2, 則 p 的 否定敘述 為. 5. 笛摩根定律 ( De Morgan s law ) ~ ( p q) ~ p ~q ~ ( p q) ~ p ~q 複合敘述的否定敘述 例 3: 設 X 是老師,下列哪些是 X 是男性且 X 教數學 的否定敘述? (1) X 不是男性且 X 不教數學. (2) X 不是男性或 X 不教數學. (3) X 不是男性或 X 教英文. (4) X 是女性或 X 不教數學. 隨堂練習 : 設 x 是實數,下列哪些是 x< 0 或 x> 1 的否定敘述? (1) x 0 或 x 1. (2) x 0 且 x 1. (3) x 0 或 x 1. (4) x 0 且 x 1 習題 - 觀念題 :( ) 2. 敘述 投籃 10 次至少投進 4 次 的否定敘述為 投籃 10 次至多投進 4 次. 習題 - 基礎題 :1. (1) 設 x 是實數,試寫出 x> 1 且 x< 3 的否定敘述. (2) 設 a, b 是實數,試寫出 a< 0 或 b 0 的否定敘述. 2
乙 集合集合及其運算 1. 何謂 集合? 何謂 元素? 2. 如何表示一個集合? 例 : A= { 2, 4,6,8} B= { 1,3,5,7,9} { 2, 1 4, } A= x x= k k k為正整數 { 10 } B= x x是是於的正奇數 集合的表示 2 問題 :(1) 利用列舉法表示集合 A= { x x = 9} (2) 利用描述法表示所有是於 100 且被 4 除餘 1 的正整數所組成的集合 註 : 習慣上, 我們用符號 N 表示所有正整數正整數所成的集合 ; Z 表示所有整數整數所成的集合 ; Q 表示所有有理數有理數所成的集合 ; R 表示所有實數實數所成的集合 ; C 表示所有複數複數所成的集合 3 2 例 5: 設集合 S = { x R x + x 2x 2= 0},試寫出 S 的所有元素 隋堂練習 : 設集合 S= { n Z n 是大於 30 的質數 },下列哪些元素屬於 S? (1) 21 (2) 29 (3) 41 (4) 91 (5) 139 3. 若集合 A 中的每一個元素都屬於集合 B, 則稱 A 為 B 的 部分集合部分集合. ( 或子集 ) 用符號 A B ( 讀作 A 包含於 B). 而 A 不包含於 B 時, 記為 A B. 例 :(1) { 1,2,3} { 1, 2,3, 4,5} (2) { 1,2,3} { 1, 2, 4,5} (3) { x 1< x< 3 } { x 1< x 4} (4) N Z Q R C 註 : 試問 A= { 1,2,3} 是否包含於 B { x 1 x 3, x } = 是正整數? 3
問題 : 設集合 A= { 1,2}, B= { 1, 2,3,6}, C { x x 6 } = 為的正因數, 選出正確的選項 : (1) A B (2) A C (3) B C (4) C B (5) B= C 4. 同時在集合 A 與集合 B 中的元素所構成的集合, 稱為 A 與 B 的交集, 以符號 A B 表示. 5. 在集合 A 中或是在集合 B 中的元素所構成的集合, 稱為 A 與 B 的聯集, 以符號 A B 表示. 例 :(1) 若 A= { 1, 2,3,4,5}, B= { 2,4,6,8}, 則 A B= { 2,4}, A B= { 1, 2,3, 4,5,6,8} (2) 若 S = { x 1< x< 3}, T { x 2 x 4} =, 則 S T =? S T =? 6. 在集合 A 中, 但不在集合 B 中的元素所組成的集合, 稱為 A 對 B 的差集. 以符號 A B 表示 例 :(1) 若 A= { 1, 2,3,4,5}, { 2,4,6,8} B=, 則 A B =? B A =? 7. 條列式的定義有時不易理解, 在此我們引入 文氏圖文氏圖 (Venn diagram), 提供較為視覺化的方式來 幫助理解集合的包含 交集 聯集與差集 : 註 : 從圖形中, 我們可以看出當兩個集合間沒有包含於的關係時, 就產生了交集 聯集與差集的概念 8. 試問 : 若 A { 1, 2,3 }, B { 4,5,6} = =, 則 A B =? 集合的包含 交集 聯集與差集 例 6: 設集合 A= {1, 2, 3, 4}, B= {2, 4, 6, 8, 10},試求 A B, A B, A B, B A 隋堂練習 : 設集合 A= {1, 3}, B= {2, 4, 5, 6},試求 A B, A B, A B, B A 習題 - 基礎題 :3. 設 A 是所有 20 的正因數所組成的集合, B 是除以 3 餘 2,且不大於 20 的正偶數所組成的集合. (1) 試用列舉法寫出集合 A, B. (2) 試求 A B, A B, A B 及 B A 習題 - 觀念題 :( ) 3. 設 A, B 為集合,則 A B= ( A B) ( B A) 註 : 如果我們把集合彼此之間的 交集 聯集或差集 當做是一種 運算運算, 如同加法或乘法. 那麼三個集合如果用 交集 聯集或差集 串在一起, 其中的意思是? 4
例 7: 設集合 A= {1, 2, 3, 4}, B= {1, 2, 4, 5, 6}, C= {2, 4, 5, 8},求 A B C 及 A B C 隋堂練習 : 設集合 P= { a, b, c, d, e}, Q= { c, d, e, f }, R= { f, g, h},求 P Q R 及 P Q R 9. 問題討論中, 所探討的集合們都是某個集合 U 的子集時, 則稱 U 為宇集. 舉例來說, 在前面 (P.2) 我們曾經提過一個問題 : 設正整數 n 10,已知 n 不是 2 的倍數且 n 不是 3 的倍數,試舉出所有可能的 n. 在這個問題中, 我們要探討的是在 正整數 n 10 的這個集合中, 符合條件要求的 n 有幾個. 令 S = { x x是正整數, x 10}, A= { x 1 x 10, x是 2 的倍數 }, B= { x 1 x 10, x是 3 的倍數 } 則 S 就是宇集. 而在 S 中但不在 A 中的元素所構成的集合, 稱為 A 在 S 中的補集. 用符號 A ' 表示.( 或用 A ) 即 A' { x x S, x A} =. 所以在此題中, 題目所求就是在集合 A' B ' 中有幾個元素. 10. 笛摩根定律 ( De Morgan s law ) A' B ' = ( A B)' A' B ' = ( A B)' 問題 : 可以推廣到三個集合嗎? 11. 在本節稍後的排列組合問題中, 我們將焦點擺在 集合元素的計數集合元素的計數, 也就是數一數集合中有幾個 元素. 因此, 我們引入符號 A 來表示有限集合 A 中的元素個數. ( 有些書是用 n( A ) ) 例 : 若宇集 S = { x 1 x 100, x N }, A { x x S, x 4 } 則 A =, A' =. = 是的倍數, 集合的補集與笛摩根定律 例 8: 令宇集 U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, A= {1, 3, 5, 7}, B= {2, 3, 4, 5, 6},試寫出 A 及 B 隋堂練習 : 令宇集 U = { 春, 夏, 秋, 冬 }, S = { 春, 秋 },試寫出 S 及 U. 隋堂練習 :(1) 宇集 U 及集合 A, B 如右圖所示,試用藍筆標示 A, 紅筆標示 B,觀察 A 與 B 的重疊處 ( 即 A B ) 是否恰為 A B 的補集 ( A B ). (2) 宇集 U 及集合 A, B 如例 8,寫出 A B, 並檢驗 ( A B ) 是否為 A B. 習題 - 觀念題 :( ) 4. 設 A, B, C 為集合,則 ( A B C) = A B C 5
12. 最後, 我們介紹另一個集合的概念 : 積集合 若 A= { abc,, }, { 1,2} 規定 A B B=, 我們定義一個集合的運算, 是一個新的集合, A B {( a,1),( b,1),( c,1),( a,2),( b,2),( c,2) } A B 稱為 A 與 B 的積集合. =, 積集合 例 9: 設集合 S= { x, y}, T = {1, 2, 3, 4},試求 S T 及 T S 隋堂練習 : 設集合 A= {J, Q, K}, B= {,,, },試求 A B 及 B A 例 10: 設 A= {0, 1},試求 3 A 隋堂練習 : 設 S= { 上, 中, 下 },試求 S 2 丙 基本計數原理 接下來, 我們將進入本節中最重要的部份 : 計數問題的原理. 在處理計數問題時, 我們時常交互使用下列四項看似乎簡單的法則 : (1) 窮舉法與樹狀圖. (2) 加法原理. (3) 乘法原理. (4) 取捨原理.( 又稱排容原理或容斥原理, Principle of Inclusion-Exclusion) 在此我們用下面幾個問題來說明 : (1) 如果從 A 地到 B 地有三條路可走,B 地到 C 地有兩條路可走, 試問從 A 地經 B 地到 C 地, 有幾 種不同的走法? (2) 是明要吃下午茶了, 他正在考慮要吃什麼, 如果吃蛋糕, 有巧克力 草莓 香草三種選擇 ; 如果 吃肉包, 有燒肉與蔬菜兩種口味 ; 如果吃熱狗, 有起司 麻辣 原味三種, 是明正在減肥, 只能 吃挑一種吃, 請問是明有幾種選擇? (3) A 城到 B 城之間有甲 乙 丙 丁 戊五城, 其間連結的道路 如右圖所示 今從 A 城出發走向 B 城, 要求每條道路都要經過 而且只經過一次, 則總共有幾種走法? (4) 從 1~100 中, 共有幾個整數不被 2 也不被 3 整除? 6
在面對計數問題上, 我們時常使用到上述的四個原則, 我們將透過下面課本的例題中, 來做示範. 窮舉 加法與乘法原理 例 11: 設集合 S= { n N n 是是於 30 的質數 },求 S 隨堂練習 : 設集合 T = { n Z n 是是於 100 的平方數, 且 n 除以 5 餘 1},求 T 例 17: 設集合 A= { a1, a2, a3, a4}, B= { b1, b2, b3},求 A B. 隋堂練習 : 設甲地到乙地有 4 條路,乙地到丙地有 3 條路,問從甲地經乙地到丙地有幾條不同路線 可走? 例 18: 是英有 3 件上衣, 4 件長褲, 2 雙鞋,那麼這三者之間的搭配有幾種? 隋堂練習 : 英文大寫字母 A, B, C,, Y, Z 共 26 個,若欲編製 3 字母的車牌 ( 如 ABC, AAB), 可以有多少種車牌? 例 19: 從 {1, 2, 3, 4, 5} 中取出兩個相異數字做成二位數,有多少不同的數? 隋堂練習 : 班上 40 位同學中,要選 1 人做班長,選另 1 人做副班長,可有多少種選擇? 在一般常見的計數問題中, 往往不是只用到單一原則來解決, 經常問題中需要乘法與加法一起使用. 加法原理的本質就是 分類分類, 乘法原理的本質就是 逐步思考逐步思考 在不少排列組合的問題中, 我們會先用分類, 而每一類再分別求出來 樹狀圖或窮舉法可以幫助我們更加確定答案, 並避免重複計數. 下面我們將上述的例題做些修改, 同學試著做看看 : (1) 如右圖所示, 從甲地到乙地有幾種走法? (2) 從 {0, 1, 2, 3, 4} 中取出兩個相異數字做成二位數,有多少不同的數? (3) 某公司生產多種款式的 阿民 公仔, 各種款式只是球帽 球衣或球鞋顏色不同 其中球帽共有黑 灰 紅 藍四種顏色, 球衣有白 綠 藍三種顏色, 而球鞋有黑 白 灰三種顏色 公司決定紅色的球帽不搭配灰色的鞋子, 而白色的球衣則必須搭配藍色的帽子, 至於其他顏色間的搭配就沒有限制 在這些配色的要求之下, 最多可有幾種不同款式的 阿民 公仔? 96 學測 (4) 某地區的車牌號碼共六碼, 其中前兩碼為 O 以外的英文大寫字母, 後四碼為 0 到 9 的阿拉伯數字, 但規定不能連續出現三個 4 例如 :AA1234,AB4434 為可出現的車牌號碼 ; 而 AO1234,AB3444 為不可能出現的車牌號碼, 則所有第一碼為 A 且最後一碼為 4 的車牌號碼個數為 (A) 3 25 9 (B) 2 25 9 10 (C) 25 900 (D) 25 990 (E) 25 999 97 學測 7
(5) 從一個 10 人的俱樂部, 選出一位主任, 一位幹事和一位會計, 且均由不同出任, 如果 10 人中的 甲君和乙君不能同時選上, 那麼共有種選法 88 社會 隨堂練習 : 設有 8 粒牛奶糖,要分裝成 3 包 ( 每包至少 1 粒 ),有幾種分法? 例 12: 設三角形的周長為 15,且三邊長皆為整數,問其邊長的組成有多少種? 取捨原理 例 14: 學校辦親師座談會,班上有 15 個同學的爸爸出席,有 20 個同學的媽媽出席,又其中有 5 個同學是爸爸 媽媽聯袂出席,那麼請問 : (1) 出席親師會的家長共有幾人? (2) 有家長出席親師會的同學有幾人? 隨堂練習 : 在例 14 中, 爸爸出席親師會, 而媽媽沒來的同學有幾人? 例 15: 設 n 是不大於 100 的正整數,集合 A, B 如下 : A= { n n 是 2 的倍數 }, B= { n n 是 3 的倍數 }.求 (1) A B. (2) A B 隋堂練習 : 設 n 是不大於 100 的正整數,問 (1) 使 (2) 使 n 不是最簡分數的 n 有幾個? 15 n 是最簡分數的 n 有幾個? 15 習題 - 基礎題 :6. 不大於 100 的正整數中,試求 : (1) 4 的倍數或 6 的倍數者共有幾個? (2) 4 的倍數但不是 6 的倍數者共有幾個? (3) 不是 4 的倍數且不是 6 的倍數者共有幾個? 隋堂練習 : 某次考試,班上 45 人中,國文 英文 數學不及格者依序有 8,9,10 人,國英 ( 國文與 英文 ) 英數 數國不及格者依序有 4,5,6 人,三科都不及格者 2 人,問三科都及格者 有多少人? 習題 - 基礎題 :8. 有學生 45 人參加某次體能測驗,該測驗分為 A, B, C 三項,通過 A, B, C 項者依序有 15,16,17 人,通過 AB 兩項, BC 兩項, CA 兩項者依序有 6,7,8 人,三項都通過者有 3 人,試求 : (1) 至少通過一項者有多少人? (2) 三項都沒通過者有多少人? 8
例 16: 從 1 到 1000 的所有整數中與 30 互質的有幾個? 習題 - 綜合題 : 從 1 到 100 的所有整數中,試求 : (1)2 的倍數或 3 的倍數但不是 6 的倍數者有幾個? (2)2,3,5 中之一的倍數者有幾個? (3)2 的倍數或 3 的倍數但不是 5 的倍數者有幾個? (4) 與 30 互質的有幾個? 習題 - 綜合題 : 右圖中,一大長方形等分成九個是長方形,試求 : (1) 包含 A( 紅色 ) 的長方形共有幾個? (2) 至少包含 A( 紅色 ) 的長方形或 B( 藍色 ) 的長方形共有幾個? 著色問題 例 20: 設有 5 種顏色供選用,要在下列圖案中著色,每一區域使用一種顏色,顏色可重複使用, 但相 鄰區域不得同色,圓形不可旋轉,問各有幾種著色方法? (1) (2) 隋堂練習 : 設有 5 種顏色供選用,在右圖中著色,每一區域使用一種顏色,顏色可重複使用, 但相鄰 區域不得同色,圖形不可旋轉,問有幾種著色方法? 習題 - 基礎題 : 設有 5 種顏色可供選用,要在下列圖案中著色,但每一區域使用一種顏色,相鄰區域 不得同色,圖形不可旋轉,問各有幾種著色方法? (1) (2) 問題 : 用五種不同顏色塗於右圖中, 五個空白區域, 相鄰的區域塗不同顏色, 則共有幾種塗法? 86 社會 9
除了前面 (P.6) 所述的四項原則外, 還有兩個常用的方法 : (1) 從是的數字看出規律 (2) 一對一對應原理我們用下面的例子來做說明 : 例 13: 有 10 個人參加網球單淘汰賽,每位選手只要輸一場就淘汰,每場比賽都要分出勝負,沒有和 局,最後唯一沒有輸過的人,便是冠軍.那麼總共要比賽幾場,才能產生冠軍? 隨堂練習 : 有 51 個籃球隊參加單淘汰賽,問需要比賽幾場,才能產生冠軍? 問題 : (1) 試觀察下列兩個問題之間的對應關係 : 1 是英有 3 件上衣, 4 件長褲, 2 雙鞋,那麼這三者之間的搭配有幾種? 2 多項式 ( a+ b+ c)( x+ y+ z+ u)( p+ q) 展開式有幾項? (2) 正整數 180 1 有幾個正因數? 2 所有正因數的總和為? 3 所有正因數的乘積為? (3) 試觀察下列兩個問題之間的對應關係 : 1 設有 4 種顏色供選用,要在右邊的圖案中著色,每一區域使用一種顏色,顏色可重複使用, 但相鄰區域不得同色,圓形不可旋轉,問各有幾種著色方法? 2 一家四口, 父母兄妹, 每人都會洗碗, 也會做飯, 但每餐飯, 做飯者不洗碗, 某假日午晚兩餐, 做飯者非同一人, 洗碗者也非同一人, 問有種情形 練習 : (1) 在 3 5 5 7 7 7 之中, 任取 2 個或 2 個以上的數相乘可以製照多少不同的積? (A) 20 (B) 22 (C) 24 (D) 26 (E) 30 4 (2) 正整數 10 所有正因數的乘積為? (3) 將正四角錐 S-ABCD 的每一個頂點著色, 使得相鄰的兩個頂點異色 ( 相鄰的兩個頂點, 即共用稜線的兩個頂點 ) 若只有 5 種顏色可使用, 試問共有幾種不同的著色方式? (4) 一隻青蛙 a, b, c, d, e, f 等六個相異點上跳動, 每次跳動落點異於跳點 若此青蛙從 a 點開始起跳, 跳四次後, 仍回到 a 點, 則跳法數有幾種? 註 : 實際上在處理計數問題時, 要在題目計算中去使用 一對一對應原理, 是相當有難度, 因為必須看出來 所處理的問題之間存在的一對一對應關係!!! 10
在常見的計數問題中, 有下列所謂的 捷徑問題, 在此補充 : (1) 下圖 (1) 有橫街 5 條, 縱街 4 條, 某人欲由 A 到 B 取捷徑 ( 最短路徑 ) 行走, 則共有幾種選擇方式? (2) 如下圖 (2), 某人欲走捷徑由 A 到 B, 但不可經過圖中的斜線施工區域, 則共有幾種走法? (3) 如下圖 (3), 某人欲走捷徑由 A 到 B, 但必須經過 P 點, 則共有幾種選擇方式? 圖 (1) 圖 (2) 圖 (3) 11