가, 나, 다, 세 명의 경비원이 보안을 위해 3개의 자물쇠를 구입했다. 문에 이 세 개의 자물쇠를 설치하고 해당 복제열쇠들을 나눠 갖는데, 오직 과반 이상이 참석할 때만 문을 열 수 있도록 2개씩 복사열쇠를 만들고 각자 아래 표와 같이 열쇠를 나눠가졌다.
표에서 알 수 있듯 1명은 세 자물쇠를 열 수 없지만, 2명만 모이면 모든 자물쇠를 풀 수 있다. 즉 과반이 모여야만 문을 열 수 있다.
어느날 보안업무에 라, 마, 두 명의 경비원이 추가로 배정되었다. 이제 가, 나, 다, 라, 마, 다섯 명의 경비원은 오직 과반 이상이 있을 때만 문을 열 수 있도록 추가 자물쇠와 추가 복사열쇠를 구입하려한다. 이들에게 필요한 최소 자물쇠 개수는 몇 개인가? 또 추가 복사열쇠는 어떻게 나눠가져야 하는가?
(다른 사람의 열쇠를 훔지거나, 개인이 임의로 복사열쇠를 더 만드는 등 문제에서 상정하고 있지 않은 행동들은 생각하지 않는다.)
출처: 범죄 수학(Crimes and Mathdemeanors), 리스 하스아우트
문제를 조금 각색하였습니다.
해답및 풀이
필요한 자물쇠의 개수는 10개이다. 경비원들은 추가로 7개의 자물쇠를 구입하면 된다.
우선 자물쇠가 10개 미만이면 문제가 생긴다는 것을 보이자.
가, 나, 두 사람이 문 앞의 모든 자물쇠를 열 수 있으면 과반 조건에 모순된다. 따라서 가, 나, 두 사람이 열 수 없는 자물쇠가, 혹은 자물쇠들이 있는 것이 분명하다. 이 중 하나를 골라 '가나'자물쇠라고 하자. 가, 다, 두 사람 역시 비슷한 원리로두 사람이 풀 수 없는 자물쇠, 이른바 '가다'자물쇠가 있을 것이다. 그리고 '가라', 가마', '나다', ... 이렇게 모든 두 명의 조합에 대해 그 조합이 열 수 없는 AB자물쇠가 각 조합에게 존재한다.
'AB'자물쇠의 개수는 2인조합의 수와 같으므로 5C2 = 10개이다.
만약 자물쇠가 10개 미만이면 비둘기집의 원리에 의해 두 개의 2인조합이 모두 열 수 없는 자물쇠가 존재한다. 예를 들어 '가나'도 열 수 없고, '나다'도 열 수 없는 자물쇠가 있었다고 해보자. 이 자물쇠는 가, 나, 다, 세 명이 있어도 열 수 없으므로 과반 이상이 모든 자물쇠를 열 수 있다는 조건에 모순이다. 다른 경우도 마찬가지이다. 예를 들어 '가다'도 열 수 없고 '라마'도 열 수 없는 자물쇠가 있다고 하자. 이 자물쇠는 무려 4명, 가, 다, 라, 마가 있어도 열 수 없으므로 과반조건에 모순이다.
따라서 자물쇠는 최소 10개 이상 필요하다.
위 논의를 통해 자물쇠가 10개 일 때 복사열쇠를 어떻게 나눠가져야 할 지 감을 잡을 수 있다. 10개의 자물쇠, '가나', '가다', ... , '라마' 자물쇠가 있다고 하자. '가나'자물쇠는 가와 나만 열 수 없게 하려고 하므로 이 자물쇠의 복사열쇠를 가, 나를 제외한 세 명, 다, 라, 마에게 준다. 마찬가지 방법으로 '라마'자물쇠의 복사열쇠까지 가, 나, 다에게 나눠주면 소기의 목적을 달성할 수 있다.
이상을 표로 표현하면 다음과 같다.
엄밀하게 증명하지않고 하나의 예시만 들어 풀이를 마무리한다.
예를 들어 라, 마가 문을 열려는 상황을 생각하자. 이들은 '가나', 가다', ... '다마; 총 9개의 자물쇠를 열 수 있지만, 오직 '라마'자물쇠 때문에 문을 열 수 없다. 하지만, 가, 나, 다 중 아무나 한 명이 있으면 문을 열 수 있다. 왜냐하면 '라마'자물쇠의 열쇠를 이들이 가졌기 때문이다.
