2k · 죄수 모자 문제
죄수 모자 문제
내 모자는 볼 수 없고, 앞사람들의 모자만 보인다. 그냥 찍는 것보다 나은 방법이 있을까?
맨 뒤 한 명만 운에 맡기면, 나머지는 전부 살릴 수 있을까
먼저 직접 생각해 보세요
먼저 결과를 예상해 보세요. 값을 하나씩 바꾸면서 예상과 무엇이 다른지 살펴봅시다.
바로 도전! 여섯 죄수가 일렬로 서 있습니다. 각자 앞사람들의 모자만 보여요. 맨 뒤부터 한 명씩 자기 모자 색을 답합니다(앞사람들은 그 답을 듣습니다). 당신이 여섯 명의 답을 차례로 골라 주세요. 맞히면 생존! 이 실험은 각 모자를 독립적으로 검정·흰색 반반 배정합니다. 50%는 이 모형에서의 확률이고, 나머지 n−1명의 생존 보장은 임의의 모자 배치에서도 성립합니다.
지금 답할 차례: 6번 (맨 뒤) — 앞의 모자 5개가 보입니다
생각을 정리한 뒤 해설 읽기
보이지 않는 것을 아는 방법은, 보이는 것의 규칙에 있다
이 질문이 왜 필요할까요?
여섯 사람이 일렬로 서 있습니다. 모자는 검정 아니면 흰색, 무작위예요. 각자 앞사람들의 모자만 보이고, 뒤에서부터 한 명씩 자기 모자 색을 답합니다. 앞사람들은 그 답을 들을 수 있어요.
눈으로는 절대 알 수 없습니다. 내 모자는 내 시야 밖이니까요. 그런데 약속 하나만 있으면 맨 뒤 한 명을 뺀 전원이 확실하게 살아남습니다. 그 약속이 바로 홀짝, 수학에서 패리티라고 부르는 것이에요.
홀짝은 가장 작은 정보 검사기입니다. 주민등록번호의 마지막 자리, 바코드의 검증 숫자, 컴퓨터 메모리의 오류 검출이 전부 이 문제와 같은 원리로 돌아가요. 논리가 목숨을 구하는 문제입니다.
같은 생각을 다른 말로 읽어 봅시다
첫 발언을 자신의 모자에 대한 추측으로만 쓰지 않고, 뒤 사람들에게 전달할 한 비트의 정보로 사용할 수 있습니다. 개인의 확실성과 집단이 얻는 정보를 구분해서 읽어 보세요.
예를 들어 보이는 특정 색 모자 수의 홀짝을 약속한 말로 알릴 수 있습니다. 다음 사람은 자기가 보는 모자들과 그 신호를 비교합니다. 말을 하나 들을 때마다 무엇을 새롭게 알게 되는지 추적하는 것이 중요합니다.
말 한마디에 정보 1비트를 실을 수 있다.
맨 뒤 사람의 '검정' 한 마디는 자기 모자 얘기가 아닙니다. 다섯 모자 전체의 홀짝 요약이에요. 답의 형식을 빌려 다른 정보를 보내는 것 — 이것이 부호화의 첫걸음입니다.
홀짝은 깨지면 티가 나는 약속이다.
전체의 홀짝을 알고 보이는 것과 들리는 것을 빼면, 남는 것이 내 모자입니다. 하나라도 어긋나면 홀짝이 안 맞아요. 이 민감함이 오류 검출의 원리입니다.
이제 정의와 조건을 함께 읽습니다
n−1명 생존 보장과 n명 전원 생존 보장은 다릅니다. 첫 발언자 자신의 정답은 이 전략으로 보장되지 않습니다.
전략 전체가 뺄셈 하나로 요약됩니다. 맨 뒤가 알려준 전체의 홀짝에서, 내 눈에 보이는 검정과 내 귀에 들린 검정을 빼는 것. 남는 홀짝이 곧 내 모자예요.
공식 해부 — 다섯 명을 살리는 뺄셈
= − −
맨 뒤의 약속
검정이 홀수면 '검정', 짝수면 '흰색'을 외칩니다. 자기 답의 형식을 빌려 전체의 홀짝을 방송하는 것이에요.
각자의 계산
전체 홀짝에서 보이는 것과 들린 것을 빼면 내 모자만 남습니다. 차례가 뒤로 갈수록 들린 정보가 쌓여서 계산은 늘 성립해요.
생존의 수
몇 명이든 맨 뒤 한 명만 운에 맡깁니다. 100명이면 99명 확정 — 인원이 늘어도 비용은 그대로 1이에요.
50%는 각 모자를 독립적으로 반반 배정한 실험의 확률입니다. 임의의 배치에서도 나머지 n−1명은 보장됩니다.
여기서 한 번 더 구분해 볼까요?
내 모자에 대한 정보가 없으니 각자 찍는 수밖에 없다.
내 모자를 본 사람은 없지만, 말에는 정보를 실을 수 있습니다. 맨 뒤 사람이 자기 답 대신 '보이는 검정의 홀짝'을 외치면, 그 한 마디가 앞 다섯 명 모두의 열쇠가 돼요.
맨 뒤 사람은 팀을 위해 희생된다.
첫 발언자의 생존은 보장되지 않습니다. 각 모자를 서로 독립적으로 두 색 중 반반으로 정하는 이 실험에서는 그의 생존 확률이 50%예요. 임의의 모자 배치에서도 보장되는 것은 나머지 n−1명의 생존입니다.
다른 질문에서는 어떻게 쓰일까요?
주민등록번호의 마지막 자리
앞자리들을 정해진 규칙으로 계산한 검증 숫자입니다. 한 자리를 잘못 쓰면 계산이 안 맞아 즉시 들통나요.
바코드의 검증 숫자
계산이 안 맞으면 스캐너가 '삑' 대신 다시 읽습니다. 계산대의 오류 검출이 죄수들의 홀짝과 같은 원리예요.
컴퓨터 메모리의 패리티 비트
데이터를 저장할 때 홀짝 한 비트를 덧붙입니다. 우주선(宇宙線)이 비트 하나를 뒤집어도 검사에서 걸려요.
신용카드 번호 검증
카드 번호의 마지막 자리도 검증 숫자입니다. 오타 난 번호로 결제가 시작되기 전에 걸러내요.
이번에는 내 말로 설명해 보세요
첫 발언자가 잃는 것과 뒤 사람들이 얻는 것을 나누어 설명해 보세요.
생각한 뒤 설명 확인하기
첫 사람의 말은 자기 모자를 확정하는 데 쓰이지 않지만, 나머지는 전체 홀짝 정보와 이미 들은 답을 이용할 수 있습니다.
계산과 개념을 문제로 확인하기 (4)
문제 완료 0 / 4
1. 패리티 전략을 쓰면 여섯 명 중 몇 명이 확실히 살아남을까요?
2. 맨 뒤 사람이 외치는 것은 무엇일까요?
3. 죄수가 100명이라면 확실히 살아남는 사람은 몇 명일까요?
4. 맨 뒤가 '검정 홀수'라고 외쳤습니다. 다음 차례인 죄수가 앞에서 검정 2개를 봤다면, 자기 모자는?
다음에는 어떤 질문을 해볼까요?
이전 개념
다음 개념으로 연결
관련 실험실
관련 실험실