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