推 jaye1115 :真是太強了~~~後面的例子舉完後~~ 我才看懂的 03/15 02:27
題目:
有11位科學家，要鎖機密文件，有很多鎖，每個科學家拿一部分的鎖匙，
滿足 "超過半數的人才打得開"
(1)至少要幾道鎖 (2)每個科學家拿幾隻鎖匙
打題目是因為重點在題目^^" 他是問"至少"
所以 需滿足第一點"隨便抓剛好超過半數的人 就要擁有所有鎖的鎖匙"
第二點"少於半數的人就打不開"
從第一點下去想 就某一道鎖來說 就要存在超過半數的人有它的鎖匙
從第二點下去想 就某一道鎖來說 就要存在少於半數的人沒有它的鎖匙
從第一點想 你可以想成11個人每六個人就要擁有某道鎖的鎖匙 所以要C(11,6)道鎖
也可從第二點想 想成11個人每五個人就要沒有某道鎖的鎖匙 所以要C(11,5)道鎖
所以每一道鎖 都會有六個人擁有鎖匙 那全部的人總共有6*C(11,6)把鎖匙
平均分給11人 互相牽制
ex: 比如說只有三人 甲 乙 丙 就A這道鎖來說(大寫是鎖 小寫是鎖匙)
如果只有甲有鎖匙a 那乙丙兩人就開不了(違反第二點)
所以一定要剛好超過半數的人有a 可是當甲乙有a了
若只有一道鎖 甲或乙一人就可獨開(違反第一點)
必須有第二道鎖(讓乙丙拿 防止甲獨開)
及第三道鎖(讓甲丙拿 防止乙獨開)
ex: 在舉五個人為例子 應該就超明顯了
總共要有C(5,3)=10 道鎖
每道鎖都有三個人有鎖匙 總共30把 平均分給五人 每人六把
甲 乙 丙 丁 戊 鎖=>ABCDEFGHIJ
a a a
b b b
c c c
d d d
e e e
f f f
g g g
h h h
i i i
j j j
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.26.186.99