1. 개요
죄수 100명이 등장하는 수학 퀴즈들을 모은 문서.2. 상세
죄수 100명을 데려다가 왕이나 교도관 등 높으신 분들이 게임을 제안하는 유형의 문제로, 대체로 꽤 높은 추론능력을 필요로 하는 문제들이 많다.판본에 따라 죄수들의 처우 등의 세부 내용이 달라지는데, 보통 죄수들이 게임에서 승리하면 즉시 석방되는 조건은 비슷하지만 패배했을 때는 형기가 2배로 늘어나거나 사형수였을 경우에는 즉시 사형이 집행되는 등의 차이가 존재한다. 또 문제 안에서 아예 대표 역할을 할 머리 좋은 죄수를 1명 지정해두는 경우도 있다. 물론 실제 문제를 풀 때에는 영향이 없다.
3. 문제 1 - 모자 색
죄수 100명을 일렬로 늘어세우고 검은 모자와 흰색 모자중 하나를 임의로 씌운다.[1] 각 죄수는 자기보다 앞에 있는 죄수 전원의 모자색을 볼 수 있지만 자기자신과 뒤에있는 죄수의 모자색은 알 수 없다. 여기서 뒤쪽에 있는 죄수부터 하나씩 자신의 모자색을 말해 맞췄을 경우 자신은 통과하고, 틀렸을 경우 자신만 실패한다. 죄수들은 게임이 시작되면 모자 색(검은색과 흰색) 외의 말은 할 수 없으며 해당 말도 한명당 한 번씩, 그러니깐 자신의 모자색을 맞출 때에만 할 수 있다. 사전에 100명의 죄수가 협의한다고 했을 때 최대한 많은 죄수를 통과시키려면 어떻게 해야 할까?
- [해답 보기 / 접기]
- 맨 뒤의 죄수(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번째에 있다고 가정하자.- 자신의 앞에 보이는 모자 배열에 대응되는 2진법 소수를 계산하고 [math(2^{-n})]을 곱한다. 이 결과는 첫번째 죄수가 계산한 실수의 소수점 첫 n자리를 0으로 바꾼 것과 같다.
- 그 실수를 포함하는 동치류 집합을 고른다. 그 집합에서 사전에 정해두었던 대표원을 골라낸다. 동치관계의 정의에 의해 모든 죄수는 같은 집합의 같은 대표원을 선택하게 된다.
- 그 대표원의 소수점 n번째 자릿수가 1이면 검은색을, 0이면 흰 색을 선택한다.
첫 번째 죄수가 본 모자 배열의 이진수 표현이 x라 하고 모든 죄수가 공통으로 고른 대표원을 y라고 하자. x와 y는 (동치류의 정의에 의해) 어느 자연수 k에 대해 소수점 k번째 자리수 이후의 이진수 표현은 동일하다. 위 알고리즘을 거치면 k번째 이후의 모든 죄수는 반드시 석방될 수 있다.
4. 문제 2 - 작은 방(전구)
다시 한 번 죄수 100명을 데리고 게임을 하였다. 이번에는 작은 방에서 게임이 진행된다. 게임이 시작되면 죄수들은 전부 각자 독방에 들어가며, 서로 의사소통 할 수 없다. 그리고 무작위로 죄수가 한 명씩 불려 나와 전구가 하나 있는 작은 방으로 간다. 작은 방에는 전구와 스위치만 하나 있으며 죄수는 전구를 끄거나 켤 수 있고 가만히 놔둘 수도 있으며 잠깐의 시간을 갖고 다시 독방으로 돌아간다. 죄수가 독방으로 돌아가면 다시 무작위 죄수가(한번 불렸던 죄수가 또 불릴수도 있음) 불려 작은 방으로 잠깐 들어갔다가 돌아간다. 작은 방에 있는 전구는 처음에 켜 있을 수도 있고 꺼져 있을 수도 있으며 죄수들은 그 초기 상태를 모른다.
참고로 작은 방에선 스위치를 눌러 전구를 켜고 끌 수만 있으며 다른 흔적을 남길 수 없고, 죄수들이 불릴 횟수에는 제한이 없고 불려내는 텀은 불규칙해서 죄수들은 자신이 불렸을 때 앞서 죄수가 몇 번 불렸는지도 알 수 없다. 죄수들은 언제든지 게임을 중단할 수 있는데, 만약 중단 시점에서 모든 죄수가 한 번 이상은 작은 방에 출입했다면 전원이 통과하고, 한 명이라도 작은 방에 들어가지 않은 죄수가 있으면 전원 실패한다. 게임 시작 전 죄수들이 모두 회의하는 시간을 가질 때 어떻게 해야 100% 통과할 수 있을까?
참고로 작은 방에선 스위치를 눌러 전구를 켜고 끌 수만 있으며 다른 흔적을 남길 수 없고, 죄수들이 불릴 횟수에는 제한이 없고 불려내는 텀은 불규칙해서 죄수들은 자신이 불렸을 때 앞서 죄수가 몇 번 불렸는지도 알 수 없다. 죄수들은 언제든지 게임을 중단할 수 있는데, 만약 중단 시점에서 모든 죄수가 한 번 이상은 작은 방에 출입했다면 전원이 통과하고, 한 명이라도 작은 방에 들어가지 않은 죄수가 있으면 전원 실패한다. 게임 시작 전 죄수들이 모두 회의하는 시간을 가질 때 어떻게 해야 100% 통과할 수 있을까?
- [해답 보기 / 접기]
- 게임을 중단할 대표를 한명 정한다. 그리고 나머지 죄수들이 작은 방에 들어갈때마다 행동방식을 정한다.
1. 방에 들어갔을 때 전구가 켜져 있으면 그대로 두고, 전구가 꺼져 있으면 켠다.
2. 전구를 두 번 켰다면 꺼져있어도 켜지 않고 그냥 나온다.
그리고 대표는 작은 방에 갔을 때 전구가 꺼져 있으면 그대로 두고 켜져 있으면 끈 다음 그 횟수를 기억해둔다. 그렇게 전구를 끈 횟수가 199회가 되었을 때 게임 중단을 선언하면 된다.
여기서 다른 죄수들이 두 번 전구를 켜야 하는 것과 전구를 끈 횟수가 199회가 되어야 하는 이유는 초기 전구 상태를 모르기 때문이다. 대표가 전구를 처음으로 껐을 때 그 끈 행동이 다른 죄수들이 켠 전구를 끈 것인지 처음부터 켜져 있던 전구를 끈 것인지 알 수 없다. 따라서 죄수들이 한 번만 켜고 끈다면 그 횟수가 누락될 가능성이 있으므로 죄수는 두 번씩 켜야하며, 대표가 처음에 끈 것은 횟수가 죄수들이 켠 것에 카운트되지 않으므로 나머지 99명의 죄수가 2번씩 켠 198회에 처음 대표가 끈 전구 1회를 더해 199회가 된다.
5. 문제 3 - 작은 방(사물함)
또 다시 죄수 100명을 데리고 게임했다. 그만해 이번의 게임은 사물함이 일렬로 100개 늘어서 있는 작은 방에서 진행된다. 죄수들은 1번부터 100번까지 번호가 부여되고, 사물함에는 각각 1부터 100까지 숫자가 적힌 종이가 무작위로 들어있다.[3] 죄수들은 회의 후 게임이 시작되면 각자 독방으로 들어가 소통할 수 없으며 시간마다 무작위로 한명씩 불려나와 작은 방으로 간다. 거기서 죄수는 50개의 사물함을 선택해서 열고 안의 종이에 적힌 번호를 확인할 수 있는데, 만약 50개의 사물함 중 자신의 번호가 적힌 종이가 나오면 통과한다. 통과하면 나머지 죄수 중 무작위 죄수가 불려나와 똑같이 50개를 열고 자기 번호의 종이가 있으면 통과하는 것을 반복한다. 이렇게 100명이 전부 통과할 경우 죄수들은 전부 통과하지만 한명이라도 자신의 번호가 나오지 않는다면 전원 실패한다.
참고로 작은 방에는 간수들이 있어 죄수들이 지나갈 때마다 처음 상태로 말끔히 돌려놓기 때문에 사물함을 열어놓거나 종이를 접는 등의 어떠한 흔적을 남기는 것도 불가능하다. 죄수들이 통과할 확률을 최대한 높이려면 어떻게 해야 할까?
참고로 작은 방에는 간수들이 있어 죄수들이 지나갈 때마다 처음 상태로 말끔히 돌려놓기 때문에 사물함을 열어놓거나 종이를 접는 등의 어떠한 흔적을 남기는 것도 불가능하다. 죄수들이 통과할 확률을 최대한 높이려면 어떻게 해야 할까?
- [해답 보기 / 접기]
- 각 죄수들은 자기의 번호에 맞는 사물함을 세어서 그걸 먼저 열고,(왼쪽부터 셀 지 오른쪽부터 셀 지는 알아서 정한다) 열어서 번호가 나오면 그 번호에 맞는 사물함을 세어서 여는 것을 반복하면 된다.
죄수들이 자기 마음대로 사물함을 연다면 통과할 확률은 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. 기타
이 문제들 중 일부는 문제적 남자에 출제된 적이 있었다. 문제 1의 경우 푸는데 3시간이 걸렸다.7. 관련 문서
[1] 모자의 개수는 정해져 있지 않으므로, 100명 모두 검은색이나 흰색 모자가 씌워지는 것도 가능하다.[2] 여담으로, 이는 선택공리를 가정했을 때 구축할 수 있는 비가측집합의 예시인 비탈리 집합의 정의 방법과 비슷하다. 즉, 문제를 풀기 위해서는 선택공리가 필수 불가결하다는 소리이다.[3] 당연하지만 종이 외의 다른 물건은 없다.