Re: [中學] 排列組合
※ 引述《justin0602 (justin)》之銘言：
: 有11位科學家'共同研究某秘密計畫
: 其中之資料妥善擺在安全櫃當中
: 只有當超過半數的人在時才能打開此安全櫃
: 因為安全櫃安置若干不同鎖
: 而每一個科學家都有這些鎖的部份鑰匙
: 請問至少要配上多少鎖
: 而每位科學家至少需要多少鎖匙
: 才能保全安全櫃並能開啟
假設 n 個科學家,有 m 個不同的鎖,每個科學家有 x 把鑰匙
Case I:n = 2k+1 是奇數,過半數要 k+1 個科學家到場
m個不同的鎖,x把不同的鑰匙,有 C(m,x) 種組合,
其中每一個鎖都有 x*n/m 把鑰匙
所以來的科學家每個鎖要有一位 C(m,x)-(x*n/m) +1≦k+1
=> C(m,x)-(x*n/m) ≦ k
Ex1: n = 5 = 2*2+1 => k = 2, m = 4, 求x=?
Sol:C(4,x)-(x*5/4) ≦ 2 => x = 3
ΟΟΟΟ
ΛΛΛ
ΛΛΛ
Ex2: n = 5 = 2*2+1 => k = 2, m = 5, 求x=?
Sol:C(5,x)-(x*5/5) ≦ 2 => x = 4
ΟΟΟΟΟ
ΛΛΛΛ
ΛΛΛΛ
Case II:n = 2k 是偶數,過半數要 k+1 個科學家到場
m個不同的鎖,x把不同的鑰匙,有 C(m,x) 種組合,
其中每一個鎖都有 x*n/m 把鑰匙
所以來的科學家每個鎖要有一位 C(m,x)-(x*n/m) +1≦k
=> C(m,x)-(x*n/m) ≦ k-1
Ex1: n = 4 = 2*2 => k = 2, m = 4, 求x=?
Sol:C(4,x)-(x*4/4) ≦ 1 => x = 3
ΟΟΟΟ
ΛΛΛ
ΛΛΛ
ΛΛ Λ
Ex2: n = 6 = 2*3 => k = 3, m = 5, 求x=?
Sol:C(5,x)-(x*6/5) ≦ 2 => x = 4
ΟΟΟΟΟ
ΛΛΛΛ
ΛΛΛΛ
Λ ΛΛΛ
ΛΛ ΛΛ
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.170.217.25
討論串 (同標題文章)
