모자 색 맞히기
앞사람 모자만 보고 맞혀 보세요
세 사람이 앞을 보고 일렬로 서서 빨간 모자나 파란 모자를 무작위로 씁니다. 앞사람 모자는 보이지만 자기 모자와 뒷사람 모자는 볼 수 없습니다.
맨 뒷사람부터 차례로 자기 모자 색을 외치는데 미리 짠 전략 하나만으로 앞사람들이 100% 자기 모자를 맞히는 기적이 일어납니다. 보이지도 않는 내 모자 색을 어떻게 확신할 수 있을까요?
이야기
줄 맨 뒤에 선 사람의 처지를 생각해 보십시오. 그는 앞사람들의 모자를 다 보지만 자기 것은 못 봅니다. 그가 외치는 「빨강」은 자기 모자에 대한 말이 아니라 앞사람들에게 보내는 신호입니다.
그런데 여기서 이 문제의 진짜 얼굴이 드러납니다. 그는 자기 목숨을 걸고 신호를 보내는 것입니다. 그가 맞을 확률은 딱 절반입니다. 한 사람이 동전 던지기에 자기를 걸어 나머지 전부를 살리는 셈입니다.
왜 앞사람들은 반드시 맞힐까요. 둘째 사람은 맨 뒤가 알려 준 홀짝과 자기가 보는 앞쪽의 홀짝을 견줍니다. 둘이 같으면 자기 모자는 파랑, 다르면 빨강입니다. 자기 모자 하나가 홀짝을 바꾸느냐 마느냐가 답이기 때문입니다.
셋째 사람은 여기에 둘째가 말한 것을 더해 홀짝을 고쳐 잡습니다. 앞사람이 하나 말할 때마다 정보가 갱신되므로, 뒤에서부터 차례로 모두가 틀림없이 맞힙니다.
QR 코드가 가려져도 읽히는 까닭입니다. 자료에 짝홀 정보를 덧붙여 두면 일부가 망가져도 되살릴 수 있습니다.
휴대전화 통화, 위성 사진 전송, 하드디스크, CD의 흠집 — 오류 정정 부호가 없으면 어느 것도 제대로 안 됩니다.
계단 넷 — 같은 사실을 네 깊이로
모자 두세 개로 해 본다
친구 셋이 앞을 보고 줄을 섭니다. 맨 뒤 친구는 앞의 두 모자가 다 보이고, 가운데 친구는 맨 앞 모자만 보입니다.
만약 앞의 두 모자가 같은 빨간색이라면 맨 뒷사람은 쉽게 상황을 파악합니다. 하지만 둘의 색이 다르면 어떻게 해야 할까요? 뒷사람이 외치는 한마디를 단순한 답이 아니라 앞사람을 위한 비밀 암호 신호로 쓰기로 약속하면 모두를 살릴 수 있습니다.
아무렇게나 찍으면
「모르겠다」고 말할 수 있게 하면 됩니다.
앞사람이 준 신호 읽기
열 명이 줄을 섰을 때 맨 뒷사람은 자기 앞의 빨간 모자 개수를 전부 셉니다. 빨간 모자가 짝수 개면 '빨강', 홀수 개면 '파랑'이라고 외치기로 사전에 약속합니다.
맨 뒷사람은 50% 확률로 맞히거나 틀리지만, 그 앞의 아홉 명은 뒷사람의 외침으로 전체 빨간 모자의 홀짝(패리티)을 완벽히 알게 됩니다. 아홉 번째 사람은 자기 앞의 빨간 모자 개수와 비교하여 자기 모자 색을 100% 알아맞히고, 이 정보가 도미노처럼 앞으로 전달됩니다.
약속을 정해 보세요
이기는 경우를 모으고 지는 경우를 한곳에 몰아넣는 것이 요령입니다.
패리티(짝홀) 규약
이 전략의 핵심은 이진법 체계의 패리티 비트(Parity bit) 원리입니다. 각 모자를 0(파랑)과 1(빨강)로 대응시키면, 명의 모자 색 벡터 에서 맨 뒷사람이 앞선 개 성분의 합 를 외쳐 주는 것입니다.
각 사람은 이전 사람들이 부른 값들과 자기 앞의 합을 차감하여 로 자기 값을 유일하게 복원합니다.
해밍 부호로 넓혀 보세요
오류정정부호가 그대로 모자 문제의 답이 됩니다.
오류 정정 부호
모자 맞히기 퍼즐은 정보이론의 해밍 부호(Hamming Code) 및 오류 정정 부호(Error-Correcting Codes)와 직결됩니다. 3명, 7명, 명이 동시에 모자를 쓰고 동시에 외쳐서 최소 한 명 이상 맞히는 문제는 초입방체(Hypercube) 위의 독립 집합 및 구 덮기(Sphere covering) 문제입니다.
현대 통신과 메모리 반도체는 전송 중 깨진 1비트의 오류를 이 패리티 검사 행렬을 통해 실시간으로 탐지하고 스스로 복구합니다.
무한 명이라면
무한 명일 때는 선택공리가 필요합니다 — 그러면 유한 명만 틀립니다.
풀어 보기
모자 색 맞히기와 패리티 전략. 세 사람 1번(맨 앞), 2번(중간), 3번(맨 뒤)이 앞만 보고 줄을 서 있다. 빨간 모자는 1, 파란 모자는 0이라 하자. 3번은 앞의 두 모자 번호의 합이 짝수이면 '파랑', 홀수이면 '빨강'을 외치기로 했다.
(1) 1번이 빨간 모자(1), 2번이 파란 모자(0)를 쓰고 있을 때 3번이 외쳐야 할 색을 쓰시오.
(2) (1)에서 3번의 외침을 들은 2번이 1번의 빨간 모자(1)를 보고 자신의 모자 색을 정확히 맞히는 논리적 과정을 쓰시오.
(3) 100명이 줄을 섰을 때 이 패리티 전략을 사용하면 100% 확실하게 자기 모자 색을 맞히는 사람은 최소 몇 명인지 구하시오.
(1) 1+0=1(홀수)이므로 '빨강', (3) 맨 뒷사람을 제외한 99명이 100% 맞힙니다.
답과 풀이 보기
(1) 빨강입니다.
은 홀수이므로 약속대로 '빨강'을 외칩니다.
⛔ 3 번은 자기 모자를 맞히려는 것이 아닙니다. 앞사람들에게 정보를 넘겨주는 것입니다.
(2) 2 번의 머릿속은 이렇습니다.
· '빨강'을 들었다 → 1 번과 나의 합은 홀수다
· 앞을 보니 1 번은 빨강(1) 이다
· 그러면 이므로 내 것은 짝수 = 0
· 그러므로 나는 파랑이다
확실히 맞힙니다 — 운이 아닙니다.
(3) 99 명입니다.
맨 뒷사람만 자기 모자를 볼 수도 들을 수도 없어 절반의 확률로 맞힙니다.
그 앞의 99 명은 모두 100% 맞힙니다.
· 두 번째 사람 : 맨 뒷사람의 외침 − (자기가 보는 98 명의 합)
· 그 앞 사람 : 위 외침 − (앞의 97 명) − (방금 들은 답)
이렇게 앞의 답을 모두 들으며 한 사람씩 확실하게 풀어 갑니다.
한 사람이 절반의 위험을 대신 지는 대가로 99 명이 확실히 살아납니다.
정보는 단 한 마디(빨강/파랑)뿐이었습니다. 그 한 비트에 99 명분의 답이 실려 있었습니다.
더 멀리
이것이 바로 오류 정정 부호의 원리입니다.
- 패리티 비트 — 자료에 짝홀 정보를 하나 붙여 오류를 잡습니다
- QR 코드 — 일부가 가려져도 읽히는 까닭이 이것입니다
- 직접 해 보기 — 종이 모자로 다섯 명이 해 보면 정말 됩니다
이어지는 장
다른 사람의 모자 색에서 전체의 패리티 정보를 묶어내는 전략은 서랍에 양말을 넣을 때 반드시 겹침이 발생하는 원리와 맞닿아 있습니다 — 제98장 과 함께 읽으면 정보 묶음의 힘이 더 또렷해집니다.
영감을 받은 곳
토드 에버트(Todd Ebert)의 1998년 UC 샌타바버라 박사학위 논문 「Applications of Communication Complexity to Social Software」와 엘윈 벌레캠프(Elwyn Berlekamp)의 해밍 부호 응용 연구에서 왔습니다.