조합이론에는 아주 간단한듯 보이지만 풀려면 어렵고 막상 답을 보면 허무한 그런 문제들이 많죠.. 그래서 그냥 심심할때마다 그런 문제들을 하나둘씩 공유해볼까 합니다. 오늘의 문제는 죄수 문제! 참고로 이 문제들은 조합이론에선 유명하다면 유명한 문제들로 그냥 구글 이런데서도 찾아보실수 있을겁니다.
*혹시 더 생각하고 싶으신분들을 위해서 답안은 검은색 칠을 해놓을 테니 클릭+스크롤해서 읽으세요.
문제: 어느 나라에 사형선고를 받은 죄수가 100명이 있다. 간수가 어느날 이 100명에게 1~100사이의 숫자중 하나가 적힌 종이를 나눠준다. (참고로 각 죄수가 받는 숫자는 반복되지 않음. 즉, 100명의 죄수는 전부 서로 다른 숫자가 적힌 종이를 받는다.) 그 뒤에 간수는 100개의 서랍에 무작위로 1~100까지의 번호가 적힌 종이를 하나씩 넣는다. (물론 마찬가지로 100개의 서랍에는 전부 다른 숫자가 적힌 종이가 들어간다.) 그리고 간수는 다음과 같이 제안한다.
1번 죄수를 시작으로 각 죄수는 총 50개의 서랍을 열어볼수 있다. 만약 1번 죄수가 50개의 서랍을 모두 열기전에 자신의 번호가 적힌 종이가 든 서랍을 연다면 이제 2번 죄수가 들어가 똑같은 방식으로 서랍을 연다. 이렇게해서 만약 100명의 죄수가 모두 종이를 찾아낸다면 100명의 죄수는 모두 사형을 면하지만 한명이라도 실패한다면 모두 사형을 당한다.
그 외 자잘한 사항들:
1. 서랍을 열어본 죄수는 다른 방에 따로 격리되므로 죄수들은 정보를 공유할수 없다.
2. 죄수가 서랍을 열어본 뒤에 간수는 종이를 섞지 않은 채로 그냥 서랍문만 닫는다.
자, 어떻게 하면 죄수들은 가장 높은 확률로 사형을 면할수 있을까? 가장 간단한 대답을 먼저 찾아보자:
답1. 모든 죄수가 무작정 아무 서랍 50개를 연다. 그렇다면 각 죄수가 자신의 번호를 찾을 확률은 당연히 1/2이므로 100명의 죄수가 모두 통과할 경우의 수는 고작 (1/2)^100 뿐이 되지 않는다.
하지만 이 확률은 조합이론을 이용해 상당히 올릴수 있습니다.
답2. 이론은 일단 제쳐두고 어떤 방식을 이용해야 하는지 알아보자. 1번 죄수는 들어가서 1번 서랍을 열어본다. 그리고 1번 서랍에서 1이 아닌 다른 숫자가 나온다면 그 숫자의 서랍을 연다. 그리고 이 서랍에 1이 아닌 다른 숫자가 있다면 다시 그 숫자가 적힌 서랍을 연다. 이미 그 서랍의 번호는 이전 서랍에서 나왔으므로 서랍의 번호와 종이의 번호가 똑같을 수는 없다. 이런 식으로 반복한다면 100명의 죄수가 모두 50번안에 자신의 숫자를 찾을 확률은 무려 30%가 넘어간다.
왜일까? 개념 자체는 간단하다. 만약 내가 n개의 숫자를 가지고 cycle을 생성한다 생각해보자. 이때 cycle의 길이에 제한이 없다고(물론 n개의 숫자만 있으므로 n을 넘어갈순 없다.) 가정하고 임의로 cycle들을 생성해냈을때 이 중 하나의 cycle이 길이 m을 가질 기대치는 1/m이다. 이 사실을 증명해내는 것 자체는 조합이론의 기본적 상식만 있다면 가능하지만 그 기본적 상식들을 증명하거나 이해하는것은 조금 어려운 편이라고 생각한다. 여하튼 이 기대치를 가지고 만약 임의로 cycle들을 생성했을때 최소 하나의 cycle의 길이가 n/2를 넘어갈 확률을 구하면 약 69%로 수렴된다. 즉 약 31%의 확률로 임의로 생성된 cycle들의 길이는 모두 n/2 이하가 되므로 위에 방식대로 서랍을 열어본다면 모든 죄수가 자신의 번호를 찾을 확률은 30%가 넘어간다.
*죄수가 서랍을 연뒤에 간수는 종이를 다시 섞지 않으므로 cycle들은 처음에 한번 생성된 것이나 마찬가지이다.
