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