題目: 有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