100명의 죄수와 상자
상자 50개로 살아남기
상자 백 개에 1번부터 100번까지의 번호표를 무작위로 하나씩 넣고 닫으세요. 이제 백 명의 죄수가 각자 상자를 쉰 개씩 열어 자기 번호를 찾아야 합니다.
각자 아무렇게나 열면 모두가 성공할 확률은 로또 1등보다 아득히 낮습니다. 하지만 앞사람이 열었던 길을 번호대로 따라가기만 하면 성공 확률이 31%를 훌쩍 넘는 까닭은 무엇일까요?
이야기
2003년, 안나 갈과 페테르 브로 밀테르센이 쓴 논문에 이 문제가 실립니다. 그런데 그 논문은 감옥 이야기가 아니라 컴퓨터가 자료를 어떻게 저장하는가에 대한 것이었습니다. 이 풀이를 찾아낸 사람은 같은 대학의 스벤 스퀴움이었습니다.
작전은 이렇습니다. 자기 번호와 같은 번호의 상자를 먼저 엽니다. 그 안에 든 번호의 상자를 다음에 엽니다. 또 그 안의 번호로 갑니다. 나온 번호를 따라 계속 가는 것입니다.
이렇게 하면 상자들이 고리를 이룹니다. 자기 번호에서 출발한 길은 반드시 자기 번호가 든 상자로 되돌아오기 때문입니다. 그러니 성공하느냐 마느냐는 「내가 속한 고리가 쉰 개보다 짧은가」 하나로 정해집니다.
그리고 여기가 핵심입니다. 쉰 개보다 긴 고리는 많아야 하나밖에 생기지 않습니다. 둘이 있으면 상자가 백 개를 넘어야 하기 때문입니다. 그래서 「모두 실패」가 아니라 전부 성공하거나 전부 그 한 고리에 걸리거나가 됩니다.
긴 고리가 생길 확률을 셈하면 약 69%이므로, 백 명이 다 같이 풀려날 확률은 31%가 넘습니다. 아무렇게나 열 때의 확률과는 비교가 되지 않습니다.
「따로따로」를 「다 같이」로 묶는 발상입니다. 각자 무작위로 하면 0인데, 같은 규칙을 따르면 31%가 됩니다.
분산 시스템에서 여러 컴퓨터가 미리 정한 같은 규칙으로 움직여 통신 없이 합을 맞추는 설계에 같은 생각이 쓰입니다.
계단 넷 — 같은 사실을 네 깊이로
카드 여섯 장으로 고리를 따라간다
카드 6장을 뒤집어 놓고 1부터 6까지 번호를 섞어 둡니다. 1번 카드를 뒤집었을 때 4가 나오면 다음에는 4번 카드를 뒤집습니다.
이렇게 나온 숫자의 자리로 계속 따라가다 보면 신기하게도 처음 시작했던 1번으로 돌아오는 닫힌 고리가 만들어집니다. 눈앞의 숫자를 길잡이 삼아 따라가는 단순한 규칙입니다.
아무렇게나 열면
그런데 31% 로 올리는 방법이 있습니다.
상자를 따라가는 규칙을 흉내 내 보기
상자에 무작위로 번호를 넣으면 전체 상자들은 여러 개의 닫힌 순환 고리로 쪼개집니다. 모든 상자는 반드시 단 하나의 고리에만 속합니다.
자기 번호가 적힌 상자부터 열어 화살표를 따라가면 죄수는 자기가 속한 고리의 상자들만 차례로 밟게 됩니다. 만약 그 고리의 길이가 50 이하라면 쉰 번 안에 무조건 자기 번호를 발견합니다. 고리 길이가 운명을 결정합니다.
고리를 따라가 보세요
사람 수를 늘려도 거의 안 떨어집니다.
순환의 길이로 확률 구하기
100개의 원소로 이루어진 순열에서 길이가 인 순환 고리는 동시에 둘 이상 존재할 수 없습니다. 따라서 길이가 인 단일 순환이 존재할 확률은 정확히 입니다.
모든 죄수가 살아남을 확률은 길이가 51 이상인 긴 순환이 없을 확률이므로 로 계산됩니다. 조화수의 차를 적분으로 근사하면 , 즉 약 31.2%가 됩니다.
긴 고리가 있으면 실패합니다
51 부터 100 까지 더하면 ln 2 = 0.693 — 실패 확률입니다.
순열의 순환 구조
이 문제는 대칭군 의 순환 분할(Cycle Index)과 결합 확률론의 정수를 담고 있습니다. 각자의 독립적 시행을 고리 구조라는 공유된 확률 공간에 동조시킴으로써 개별 실패 사건들을 강력한 양의 상관관계로 묶어 냅니다.
중앙 제어나 직접 통신 없이도 공통의 결정론적 알고리즘을 통해 집단 최적화를 달성하는 분산 합의 프로토콜 설계의 기초가 됩니다.
1 − ln 2 로 다가갑니다
1 − ln 2 = 0.30685… — 전략 하나가 불가능을 삼분의 일로 바꿉니다.
풀어 보기
100명의 죄수와 순환 고리. 다음 물음에 답하시오.
(1) 100명의 죄수가 아무 전략 없이 각자 무작위로 상자 50개를 고를 때, 100명 모두가 자기 번호를 찾을 확률을 거듭제곱 꼴로 나타내시오.
(2) 상자 추적 전략을 쓸 때, 100개의 순열에서 길이가 60인 순환 고리가 존재할 확률을 기약분수로 쓰시오.
(3) 조화수 근사 공식 을 이용하여 100명 모두 생존할 확률의 근삿값을 백분율(소수 첫째 자리까지)로 구하시오.
(1) 각 죄수의 성공 확률이 1/2이므로 입니다. (2) 입니다. (3) 이므로 약 30.7%(정밀식 31.2%)입니다.
답과 풀이 보기
(1) 입니다.
죄수 한 사람이 100 개 중 50 개를 열어 자기 번호를 찾을 확률이 이고, 100 명이 서로 상관없이 다 성공해야 하므로 곱합니다.
⭐ 이 값은 약 — 사실상 0 입니다. 우주가 끝날 때까지 되풀이해도 한 번도 안 일어납니다.
(2) 입니다.
⭐ 놀랍게도 100 개의 무작위 순열에서 길이 인 고리가 있을 확률은 입니다 (단 , 그런 긴 고리는 있어야 하나뿐이기 때문입니다).
그러니 고리가 길수록 오히려 드뭅니다.
(3) 약 30.7% 입니다.
모두 살아남으려면 길이 51 이상인 고리가 하나도 없어야 합니다.
(정확히 셈하면 31.2% 입니다.)
⭐ 아무 전략 없이는 인데, 상자를 따라가기만 해도 3 분의 1 로 뜁니다.
비결은 죄수들이 서로의 운을 묶어 버린 것입니다.
각자 아무렇게나 열면 실패가 따로따로 쌓이지만, 상자를 따라가면 모두가 같은 고리 구조 하나에 운명을 겁니다.
그러면 다 살거나 다 죽거나가 되고, '다 사는' 쪽이 3 분의 1이나 됩니다. 확률을 바꾼 것이 아니라 확률을 한 덩어리로 묶었습니다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
「따로따로」를 「다 같이」로 묶은 것이 열쇠입니다.
- 순열의 순환 — 뒤섞기를 고리로 보는 것이 조합론의 기본입니다
- 확률 계산 — 긴 고리가 있을 확률은 조화급수로 나옵니다
- 직접 해 보기 — 카드 열 장으로 「다섯 장까지」 규칙으로 해 보세요
이어지는 장
무작위로 뽑으면 0에 가깝던 생존율이 순환 고리를 따라가면 30%를 넘습니다 — 제120장 처럼 직관을 뒤흔드는 확률의 기하학적 반전을 경험해 보세요.
영감을 받은 곳
안나 갈(Anna Gál)과 피터 브로 밀터센(Peter Bro Miltersen)이 2003년 컴퓨터 과학 학술회의(ICALP)에 낸 논문 「Cellular Automata and Information Protocols」에서 처음 제안했습니다.