排列組合3題
1. [u]正昇[/u]、[u]得志[/u]、[u]軒量[/u]、[u]噴火承浩[/u]四人去吃飯，共有9樣菜，每人選3樣[b]不同[/b]的菜，已知任[b]兩人中都有選一樣共同的菜且恰只有一樣[/b]，求選法?2. [u]正昇[/u]在2 × 7的方格中選取若干個格子塗成黑色(也可以全部不選)，使得任兩個黑色的格子都不共邊的方法有_______種。
3. 若正整數n小於1000且恰可以表示成5種j個接續正奇數之和，j≥1。試問這種n共有________個。 [size=3](以下解法若有錯誤，或另有更佳解法，敬請不吝提出)[/size]
[size=3]
[/size]
[size=3]1. 想法: 把所求分割成定義明確的互斥子集，常能簡化問題。[/size]
[size=3]
[/size]
[size=3]先考慮其中某三人 A，B，C，並將所求分割成 a. A∩B, A∩C, B∩C 皆相同; b. A∩B, A∩C, B∩C 皆相異 兩種情形。[/size]
[size=3]
[/size]
[size=3] a. A∩B, A∩C, B∩C 皆相同: 再分割成 D 是否選取了這個交集。[/size]
[size=3]
[/size]
[size=3]C(9,3)*3*C(6,2)*C(4,2)*(1*1 + 2³) = 204120[/size]
[size=3]
[/size]
[size=3]b. A∩B, A∩C, B∩C 皆相異: 再分割成 D 是否選取了某個交集(至多選取一個)。[/size]
[size=3]C(9,3)*3*C(6,2)*2²*C(4,1)*[C(3,1)*1*C(3,1) + C(3,3)] = 604800[/size]
[size=3]
[/size]
[size=3]所求 = a. + b. = 808920[/size]
[size=3]
[/size]
[size=3]
[/size] [size=3](以下解法若有錯誤，或另有更佳解法，敬請不吝提出)[/size]
[size=3]
[/size]
[size=3]2. 想法: 符合題意之 2 x n 的方格，可衍生自符合題意之 2 x (n-1) 的方格，反之亦然，這暗示了本題使用遞迴關係的可行性。[/size]
[size=3]
[/size]
[size=3]將合題意之 2 x (n-1) 的方格最右行分為 a. 二白 與 b. 一黑一白，它們各自可向右一行衍生出 a. 1 個"二白"與 2 個"一黑一白"，與 b. 1 個"二白"與 1 個"一黑一白" 之符合題意的 2 x n 方格[/size][size=3]。[/size]
[size=3]
[/size]
[size=3]若 W，G 分別表示 2 x (n-1) 方格最右行 "二白" 與 "一黑一白" 的個數，則與 2 x n 方格的[size=3][/size]遞迴關係為 (W, G) → (W+G, 2W+G)。[/size]
[size=3]
[/size]
[size=3]以下由 2 x 1 方格開始:[/size]
[size=3]
[/size]
[size=3](1, 2) → (3, 4) → (7, 10) → (17, 24) → (41, 58) → (99, 140) [/size][size=3]→ (239, 338)[/size]
[size=3]
[/size]
[size=3]所求 = 239 + 338 = 577[/size]
[size=3]
[/size]
[size=3](就本題而言，分成: 恰 0 個黑格，恰 1 個黑格，...，恰 7 個黑格討論，亦不失為一可行的方法)[/size]
[size=3]
[/size]
[size=3]
[/size] [size=3](以下解法若有錯誤，或另有更佳解法，敬請不吝提出)[/size]
[size=3]
[/size]
[size=3]想法: 利用等差級數和的性質，考慮正整數 n 的充要條件。[/size]
[size=3]
[/size]
[size=3]n = 等差級數和 = 中位數(M)*項數(N)，因此 1 種接續正奇數之和表示法，對應 1 種"兩個正整數的乘積(M*N)"，但反之不然，因為要符合:[/size]
[size=3]
[/size]
[size=3]1. 各項皆 >0，即 M > N-1。[/size]
[size=3]
[/size]
[size=3]2. 各項皆為奇數，即 M, N 奇偶性相同。[/size]
[size=3]
[/size]
[size=3]亦即，任取兩個奇偶性相同的正整數 M, N，[/size][size=3]即恰對應一個"接續正奇數之和表示法"。以下分為 a. M, N 皆奇數，與 b. M, N 皆偶數 討論。[/size]
[size=3]
[/size]
[size=3]a. M, N 皆奇數[/size]
[size=3]
[/size]
[size=3]以 n 的標準分解式思考: 考慮 n 可分為幾種"奇*奇"的情形與因數個數間的關係。因 n 恰可以表示成 5 種接續正奇數之和，即恰對應 5 組相異的 (M, N)，亦即 n 恰有 10 或 9 個因數。[/size]
[size=3]
[/size]
[size=3]再考慮 n (<1000) 的標準分解式中質因數的冪次為 (1,4) 或 (2,2)，得 n 有 5 個: 3⁴*5, 3⁴*7, 3⁴*11, 3²*5², 3²*7²[/size]
[size=3]
[/size]
[size=3]b. M, N 皆偶數[/size]
[size=3]
[/size]
[size=3]以 n 的標準分解式思考: 考慮 n 可分為幾種"偶*偶"的情形與因數個數間的關係。[/size]
[size=3]
[/size]
[size=3]先各分 1 個 "2" 給 M 與 N，則剩下的部分必恰有 10 或 9 個因數 [/size][size=3](方可構成 5 組"偶*偶")。再考慮 n/4 (<250) 的標準分解式中質因數的冪次為 (1,4) 或 (2,2)，得 n /4 有 10 個: 2⁴*3, 2⁴*5, 2⁴*7, 2⁴*11, 2⁴*13,[/size][size=3] 2*3⁴, 2²*3², 2²*5², 2²*7², 3²*5²。[/size]
[size=3]
[/size]
[size=3]所求 = a. + b. = 15 (個)[/size]
[size=3]
[/size]
[size=3]
[/size]
回復 4# cefepime 的帖子
感謝cefepime老師的詳細解釋 :) [size=3]只有第 2 題確定答案正確，其他兩題沒把握。[/size] 三題都對啦!好厲害! cefepime 兄真神人也......
小弟提供前兩題的不同想法
(1) 這題可分以下三種情形討論
(i)4人共點6樣菜
易知每樣菜恰被2人所點
\(C_{6}^{9}\times 6!=60480\)
(ii)4人共點7樣菜
其中有1樣菜恰被3人所點，有3樣菜恰被2人所點，其餘3樣菜恰被1人所點
恰被3人所點的這樣菜，有\(C_{3}^{4}\)種被點情形
\(C_{7}^{9}\times C_{3}^{4}\times 7!=725760\)
(iii)4人共點9樣菜
其中有1樣菜恰被4人所共點，其餘8樣菜恰被4人所分點
\(C_{1}^{9}\times C_{2}^{8}\times C_{2}^{6}\times C_{2}^{4}\times C_{2}^{2}=22680\)
所求 = 60480 + 725760 + 22680 = 808920
(2) 用一階遞迴來做
設\({{a}_{n}}\)表示2列n行時，符合題意的方法數
則\({{a}_{n}}=2{{a}_{n-1}}+{{a}_{n-2}}\)
其中\({{a}_{1}}=3,{{a}_{2}}=7\)
所求為\({{a}_{7}}=577\)
亦可求出\({{a}_{n}}=\frac{1}{2}\left[ {{\left( 1+\sqrt{2} \right)}^{n+1}}+{{\left( 1-\sqrt{2} \right)}^{n+1}} \right]\)
[[i] 本帖最後由 thepiano 於 2014-12-28 11:03 PM 編輯 [/i]] piano老師也好厲害!
(1)每樣菜恰被2人所點
(2)有1樣菜恰被3人所點，有3樣菜恰被2人所點
(3)有1樣菜恰被4人所共點
恰都符合"任兩人恰都只有一道菜相同"，不易想到!
頁:
[1]