100명의 죄수

1. 개요

2. 상세

3. 문제 1 - 모자 색

[해답 보기 / 접기]

맨 뒤의 죄수(100번)가 검은색과 흰색의 짝홀 비율을 알려주기로 한다. 가령 검은색 모자가 홀수면 검은색, 짝수면 (즉 흰색이 홀수면) 흰색이라고 알려주는 식이다. 그러면 그 앞에 있는 죄수(99번)는 100번이 알려준 비율에서 자신을 제외했을 경우 변화가 있는지를 토대로 자신의 모자 색깔을 알 수 있다.

가령 100번이 봤을 때 검은색 모자가 50개, 흰색 모자가 49개라고 하자. 100번은 사전에 합의한 대로 '흰색'이라고 답했다. 100번의 운명은 각자의 상상에 맡기고 99번으로 넘어가 보자. 하지만 99번이 봤을 때는 검은색 모자가 49개, 흰색 모자가 49개였다. 즉 1개(자신)가 줄어든 검은색이 바로 자신의 모자인 셈이다. 검은색 모자가 50개라면 흰색 모자가 48개일 것이므로, 이 경우 1개가 줄어든 흰색이 된다.

이런 식으로 100번은 50%의 확률로 통과하고 나머지 99명의 죄수는 100% 통과할 수 있다. 100번 그는 선한 양심수였습니다

3.1. 문제 1-1 - 무한한 죄수와 모자 색

[문제 보기 / 접기]

>자연수(즉, 가산 무한)명의 죄수들을 일렬로 늘어세우고 검은 모자와 흰색 모자를 씌운다. 즉, 모든 죄수는 그 앞의 (가산) 무한한 수의 죄수의 모자를 볼 수 있다. 룰은 이전과 동일하나 이전 죄수의 대답을 들을 수 없으며 그 대답이 맞았는지 아닌지도 알 수 없다. 사전에 모든 죄수가 협의한다고 했을 때 최대한 많은 죄수를 통과시키려면 어떻게 해야 할까?

[해답 보기 / 접기]

놀랍게도 단 유한한 수의 죄수만 실패하며 나머지 무한한 수의 죄수가 석방되는 방법이 존재한다! 그러나 문제를 풀기 위해서는 선택공리를 가정해야 한다. 방법은 다음과 같다.

문제를 단순화시키기 위해 모자 색의 배열을 검은색은 1로, 흰색은 0으로 생각해서 자신의 앞에 보이는 모자들을 이진수 소수 표현의 실수에 대응시켜 보자. 예를 들어 자신의 앞에 흑백흑백백흑백...의 모자들이 보이면 그 배열을 0.1010010... 과 같은 실수에 대응시킬 수 있다. 그리고 실수 집합 위의 동치류(equivalence class)를 다음과 같이 정의한다.

[math(x \sim y \Leftrightarrow \exists n \in \N, (x - y) 2^n \in \mathbb{Z})] [2]

이를 자연어로 풀어서 쓰면, 어떤 두 실수가 있을 때 그 두 수가 유한한 수의 (이진수) 소숫점 자리를 넘어서는 지점부터 같은 값을 가진다면, 두 수를 같은 동치류 집합에 넣겠다는 것이다. 선택공리를 가정했으므로 구간 [math([0,1])]을 위 동치류로 분할한 다음, 그 분할한 집합 각각에 대해 대표원을 하나씩 선택할 수 있다.

이 때, 모든 죄수가 사전에 이 대표원들을 모조리 외웠다고 한다면, 다음 전략에 의해 최초 유한한 수의 죄수를 제외하고 모든 죄수가 석방될 수 있다. 죄수가 n번째에 있다고 가정하자.

1. 자신의 앞에 보이는 모자 배열에 대응되는 2진법 소수를 계산하고 [math(2^{-n})]을 곱한다. 이 결과는 첫번째 죄수가 계산한 실수의 소수점 첫 n자리를 0으로 바꾼 것과 같다.
2. 그 실수를 포함하는 동치류 집합을 고른다. 그 집합에서 사전에 정해두었던 대표원을 골라낸다. 동치관계의 정의에 의해 모든 죄수는 같은 집합의 같은 대표원을 선택하게 된다.
3. 그 대표원의 소수점 n번째 자릿수가 1이면 검은색을, 0이면 흰 색을 선택한다.

첫 번째 죄수가 본 모자 배열의 이진수 표현이 x라 하고 모든 죄수가 공통으로 고른 대표원을 y라고 하자. x와 y는 (동치류의 정의에 의해) 어느 자연수 k에 대해 소수점 k번째 자리수 이후의 이진수 표현은 동일하다. 위 알고리즘을 거치면 k번째 이후의 모든 죄수는 반드시 석방될 수 있다.

4. 문제 2 - 작은 방(전구)

[해답 보기 / 접기]

게임을 중단할 대표를 한명 정한다. 그리고 나머지 죄수들이 작은 방에 들어갈때마다 행동방식을 정한다.

1. 방에 들어갔을 때 전구가 켜져 있으면 그대로 두고, 전구가 꺼져 있으면 켠다.
2. 전구를 두 번 켰다면 꺼져있어도 켜지 않고 그냥 나온다.

그리고 대표는 작은 방에 갔을 때 전구가 꺼져 있으면 그대로 두고 켜져 있으면 끈 다음 그 횟수를 기억해둔다. 그렇게 전구를 끈 횟수가 199회가 되었을 때 게임 중단을 선언하면 된다.

여기서 다른 죄수들이 두 번 전구를 켜야 하는 것과 전구를 끈 횟수가 199회가 되어야 하는 이유는 초기 전구 상태를 모르기 때문이다. 대표가 전구를 처음으로 껐을 때 그 끈 행동이 다른 죄수들이 켠 전구를 끈 것인지 처음부터 켜져 있던 전구를 끈 것인지 알 수 없다. 따라서 죄수들이 한 번만 켜고 끈다면 그 횟수가 누락될 가능성이 있으므로 죄수는 두 번씩 켜야하며, 대표가 처음에 끈 것은 횟수가 죄수들이 켠 것에 카운트되지 않으므로 나머지 99명의 죄수가 2번씩 켠 198회에 처음 대표가 끈 전구 1회를 더해 199회가 된다.

5. 문제 3 - 작은 방(사물함)

[해답 보기 / 접기]

각 죄수들은 자기의 번호에 맞는 사물함을 세어서 그걸 먼저 열고,(왼쪽부터 셀 지 오른쪽부터 셀 지는 알아서 정한다) 열어서 번호가 나오면 그 번호에 맞는 사물함을 세어서 여는 것을 반복하면 된다.

죄수들이 자기 마음대로 사물함을 연다면 통과할 확률은 2의 100승 분의 1로 사실상 불가능에 가깝다. 하지만 이렇게 하면 생존확률이 크게 높아지는데, 사이클이 50개 이하의 숫자로 이루어져 있다면 그 사이클에 번호가 있는 죄수들은 반드시 통과할 수 있기 때문이다.

예를 들어 처음 여는 죄수가 20번 사물함을 열어 그 안의 16번 종이를 보고 16번을 열고, 16번 사물함에 있는 37번을 열고, 37번 사물함에 있는 96번을 열고, 96번 사물함에서 20번 종이가 나와 통과한다면, 나중에 16번에 해당되는 죄수도 같은 방식으로 열다보면 20번의 사물함에 있는 16번 종이를 얻어 통과할 수 있으며 이는 37번, 96번 죄수들도 마찬가지이다. 이때 실패할 경우는 51개 이상의 번호로 이루어진 사이클이 존재하는 경우, 즉 50개의 사물함을 열어도 자기 번호가 나오지 않는 경우가 생길 때 뿐이다. 이 경우 한 명이라도 번호 찾기에 실패하면 해당 사이클 내의 51+명 모두가 번호 찾기에 실패하게 되고, 모두가 성공해야 생존 가능한 게임의 특성상 50명 이하의 인원들만이 실패하는 경우를 배제하게 되면 죄수들의 생존확률이 올라가게 된다. 해당 전략에 따라 실제로 계산된 죄수들의 생존확률은 약 31%다.

이렇게 보면 당연한것처럼 보이지만 모르는 사람이 보면 혼란스러울수 있는게 이 방법을 써도 정작 개인이 자신의 번호를 찾아낼 확률은 여전히 1/2라는 것과 죄수의 숫자가 수천, 수만, 무한으로 올라가도 확률이 약 30.5%까지만 내려간다는 것이다. 자세한 것은 여기서 설명하고 있다.(영어) 한국어 버전 C++ 실제 구현

6. 기타

7. 관련 문서

• 널리 알려진 퀴즈