본문 바로가기
조합론 퍼즐

보안을 위한 자물쇠의 개수는?

by Eucleides 2017. 4. 16.

  가, 나, 다, 세 명의 경비원이 보안을 위해 3개의 자물쇠를 구입했다. 문에 이 세 개의 자물쇠를 설치하고 해당 복제열쇠들을 나눠 갖는데, 오직 과반 이상이 참석할 때만 문을 열 수 있도록 2개씩 복사열쇠를 만들고 각자 아래 표와 같이 열쇠를 나눠가졌다.

표에서 알 수 있듯 1명은 세 자물쇠를 열 수 없지만, 2명만 모이면 모든 자물쇠를 풀 수 있다. 즉 과반이 모여야만 문을 열 수 있다.


 어느날 보안업무에 라, 마, 두 명의 경비원이 추가로 배정되었다.  이제 가, 나, 다, 라, 마, 다섯 명의 경비원은 오직 과반 이상이 있을 때만 문을 열 수 있도록 추가 자물쇠와 추가 복사열쇠를 구입하려한다. 이들에게 필요한 최소 자물쇠 개수는 몇 개인가? 또 추가 복사열쇠는 어떻게 나눠가져야 하는가?


(다른 사람의 열쇠를 훔지거나, 개인이 임의로 복사열쇠를 더 만드는 등 문제에서 상정하고 있지 않은 행동들은 생각하지 않는다.)


출처: 범죄 수학(Crimes and Mathdemeanors), 리스 하스아우트 

문제를 조금 각색하였습니다.



해답및 풀이