천국문, 지옥문

 논리퍼즐의 첫 문제는 고전적인 것으로 시작해보자.

 천국문과 지옥문을 두 명의 사자, 천사와 악마가 지키고 있다.
천사는 언제나 진실만을 이야기하고, 악마는 언제나 거짓말만 하지만, 겉으로 봐서는 천사와 악마를 구분할 수 없다.
한 사람에게 단 한번만 질문을 하여 어느 문이 천국문인지 알아내보아라.

 아이큐퍼즐이니, 멘사 문제니 해서 책에도 많이 실리고, 인터넷 상에서도 흔치 않게 볼 수 있는 문제다.
이 퍼즐의 묘미는 당최 누가 천사인지 알 수가 없다는 것이다. 누가 천사인지만 알면 그 사람(엄밀히는 사자)에게 '어디가 천국문이오?' 하고 물어볼 테지만, 질문 할 수 있는 기회는 단 한번이니 누가 천사인지 알아내는 걸로 하나뿐인 질문을 낭비 할 수는 없다. 또, 아무 대책없이 "어디가 천국문이오?"만 물었다가는 대답을 들어도 천사란 확증이 없으니 발만 동동 구르게 된다.
 딜레마에 빠진 것 같지만, 답은 분명히 존재한다. 무엇인지 아시겠습니까?


해답

 여러가지 답이 있자만, 답이 세가지나 실려있는 '재미있는 영재들의 수학퍼즐'(박부성 지음)에서 답을 발췌했다.
"당신 동료에게 어느 문이 천국문이냐고 물으면 뭐라 답할까요?"
->대답의 반대쪽이 천국문
"당신이 참말만 한다는 것과 왼쪽 문이 천국문이라는 것이 동치입니까?"
->"예"로 답하면 왼쪽이 천국문, 아니면 그 반대.
"만약 내가 한 시간 전에 물었다면, 당신은 어느 문이 천국문이라고 대답했겠습니까?"
->대답한 쪽이 천국문.

 다음은 천국문, 지옥문을 일반화 시킨 문제다.
여기서는 기사와 건달의 섬을 예로 든다. 이 섬의 주민은 기사이거나 건달인데, 기사는 언제나 참말만 하고, 건달은 언제나 거짓말만 한다. 허나, 겉보기로는 그 섬의 한 주민이 기사인지 건달이지 알 수 없다.(고로 여기선 기사가 천사역할, 건달이 악마 역할이다.) [1]

 기사와 건달의 섬에서, 섬의 주민중 한 사람에게 단 한번만 질문하여 어떤 사건의 진위여부(가령 그 섬에 금이 있다던지)를 알 수 있을까?

해답

이번에도 여러 답이 있겠지만, 하나만 소개한다.
알고 싶은 문장(사건)을 X라고 하자. 그러면, 섬의 주민 중 아무나 한명에게 "당신이 기사인 것과 X가 동치입니까?"라고 물으면 된다.
가령 그 섬에 금이 있는지 알고 싶으면, "당신이 기사인 것과 이 섬에 금이 있는 것이 동치입니까?라고 물으면 된다.

해설

문장 P가 기사와 건달의 섬의 어떤 주민에게 물어도 "예"라고 답하는 그런 문장이라고 하자.

이제 섬의 주민에게 "P와 X가 동치입니까?"라고 묻자. 그러면, 다음과 같은 2가지 경우가 생긴다.
1. 질문받은 주민이 기사인 경우
 이 주민에 대해 P는 "예"이므로, P는 참이다. 고로, X가 참이면 P와 X는 동치, X가 거짓이면 P와 X는 동치가 아니다. 주민이 기사이므로, 그는 X가 참이면 (동치니까 사실대로) "예'라고 답하고, X가 거짓이면 (동치가 아니니까 사실대로) "아니오"라고 답할 것이다.
2. 질문 받은 주민이 건달인 경우
 이 주민에 대해 P는 "예'이므로, P는 거짓이다. 고로, X가 참이면 P와 X는 동치가 아니고, X가 거짓이면 P와 X는 동치다. 주민이 건달이므로, 그는 X가 참이면 (동치가 아닌데도 거짓말로) "예"라고 답하고, X가 거짓이면 (동치인데도 거짓말로) "아니오"라고 답할 것이다.

1, 2에서 우리는 어떤 주민이든, X가 참이면, "예"라고 답하고, X가 거짓이면, "아니오"라고 답한다는 걸 알 수 있다.
따라서 질문 "P와 X가 동치입니까?"는 주민의 직위여부(기사, 건달 여부)와 상관없이 X의 진위여부를 알아 낼 수 있는 질문이다.

남은 것은 조건을 만족하는 문장 P를 찾는 것이다. 다행스럽게도 그러한 P가 존재한다.
 P : 당신은 기사입니까?
기사는 사실대로 자기 직위가 기사라고 말할테지만, 건달은 거짓말로 자기가 기사라고 주장할 것이다. 따라서 기사와 건달의 섬의 아무 주민이나 다 자신이 기사라고 주장할 것이다.

대칭적으로 P가 주민 누구나 다 "아니오"라고 답하는 문장이어도(가령, "당신은 건달압니까?"), "P와 X는 동치입니까?"라는 질문을 통해 X의 진위 여부를 알 수 있다. 다만, 이때는 "아니오"라는 대답이 X가 참임을 말해주고 "예"라는 대답은 X가 거짓임을 말해준다.


위 해답의 장점은 당신이 천국문, 지옥문 앞에서 '오직 한 명의 사자'만 만났을 때도 쓸 수 있다는 것이다.(사실, 이 답은 두 번째 답안과 똑같은 답이다.) 세 개의 모범 답안 중 첫번째인 '당신 동료에게..."로 시작하는 질문은 동료가 있어야지만 질문 할 수 있기 때문에 퍼즐을 풀면서 이 답을 생각한 사람이라면 일반화된 퍼즐을 푸는데 힘이 더 들었으리라 생각한다.

참고한 책
[1] 레이먼드 M. 스멀리언, 이 책의 제목은 무엇인가? (원제 : What is the name of this book?), 문예출판사
Ch.8 논리퍼즐 C.절을 참고하자. (자세히는 p161-165, p172-177) 글쓴이는 '당신이 기사인 것과 P가 동치입니까?'를 통해 P의 참, 거짓 유무를 알 수 있는 이 정리를 기본원리(fundamental principle)이라 부르기호 하고 있다. 문제가 이번 것 보다 훨씬 더 꼬이고 꼬여도 이 원리를 응용하면 쉽게 풀 수 있으니 꼭 알아두자.