가장 어려운 논리 퍼즐

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 역사
3. 전제
4. 풀이
- 4.1. 반사실적 조건문을 이용한 풀이
- 4.2. 구체적인 풀이 단계
5. '랜덤'의 행동에 대한 다양한 해석
6. 신의 머리 폭발
참조

1. 개요

가장 어려운 논리 퍼즐은 레이먼드 스멀리언의 기사와 악당 퍼즐에서 파생된 논리 퍼즐로, 진실만을 말하는 '참', 거짓만을 말하는 '거짓', 무작위로 대답하는 '랜덤' 세 종류의 신 중 누가 어떤 속성을 가졌는지, 'ja'와 'da'라는 단어를 사용하여 질문하고 답하는 방식으로 추론하는 문제이다. 퍼즐을 풀기 위해 반사실적 조건문을 활용하거나, '랜덤'의 행동에 대한 해석을 달리하는 등 다양한 풀이 방법이 제시되었으며, 신이 대답을 거부하는 경우, 즉 "머리 폭발"을 허용하여 질문 수를 줄이는 변형된 퍼즐도 존재한다.

더 읽어볼만한 페이지

논리 퍼즐 - 노노그램
노노그램은 숫자를 이용해 칸을 칠하거나 비워 그림을 완성하는 논리 퍼즐로, 다양한 이름으로 불리며 이시다 논과 니시오 테츠야가 발명한 후 여러 형태로 출시되어 잡지로도 출판된다.
논리 퍼즐 - 웨이슨 선택 과제
웨이슨 선택 과제는 논리적 추론 능력을 평가하기 위해 규칙을 검증하는 데 필요한 카드 선택을 묻는 문제이며, 사회적 맥락에 따라 정답률이 달라지는 특징을 보인다.
퍼즐 - 다른 그림 찾기
다른 그림 찾기는 거의 동일한 두 그림에서 시각적 비교 등을 통해 서로 다른 부분을 찾아내는 퍼즐이다.
퍼즐 - 몬티 홀 문제
몬티 홀 문제는 세 개의 문 중 하나를 선택한 후 진행자가 상품이 없는 문을 열어 보여줄 때, 선택을 바꾸는 것이 유리한지를 묻는 확률 문제로, 직관과 달리 선택을 바꾸는 것이 당첨 확률을 높이는 전략임을 보여주는 확률 역설이며, 의사 결정 방식에 대한 통찰을 제공한다.
논리학 - 모순
모순은 논리학, 철학, 과학 등 다양한 분야에서 사용되는 개념으로, 서로 상반되는 두 가지 주장이나 사실이 동시에 존재하는 상태를 의미하며, 특히 헤겔과 마르크스의 변증법적 유물론에서 사물의 내재적 대립으로서 역사 발전의 원동력으로 간주된다.
논리학 - 특수
특수는 철학에서는 개별적이고 구체적인 존재를, 언어학에서는 눈에 띄는 또는 예외적인 의미를 가지며, 사회적으로 특별함이 중요하게 여겨지기도 한다.

가장 어려운 논리 퍼즐
퍼즐 정보
유형	논리 퍼즐
고안자	조지 불로스(George Boolos)
발표	하버드 철학 리뷰(The Harvard Review of Philosophy)
발표 연도	1996년
설명
내용	세 신 A, B, C는 각각 참(True), 거짓(False), 랜덤(Random) 중 하나이다. 참은 항상 진실을 말하고, 거짓은 항상 거짓을 말하며, 랜덤은 진실 혹은 거짓을 무작위로 말한다. 세 신의 정체를 밝히기 위해 세 번의 예/아니오 질문을 던져야 한다. 각 질문은 정확히 한 신에게만 해야 한다. 신들은 영어를 이해하지만, 자신들의 언어로 답하며, 그 언어에서 '예'와 '아니오'는 'da'와 'ja'이다. 어떤 단어가 '예'를 의미하는지 알 수 없다.
같이 보기
관련 항목	수수께끼

2. 역사

이 퍼즐의 원작자는 논리학자 레이먼드 스멀리언이며^[1]^[16], 퍼즐의 기반은 그의 유명한 기사와 악당 퍼즐들이다. 기사와 악당 퍼즐은 모든 주민이 항상 참말만 하는 기사 또는 항상 거짓말만 하는 악당인 가상의 섬을 배경으로 하며, 섬을 방문한 사람이 예/아니오 질문을 통해 원하는 정보를 알아내는 방식이다.^[1]^[6]^[17]

스멀리언의 여러 저서에서 유사한 퍼즐들을 찾아볼 수 있다. 예를 들어, 그의 책 ''이 책의 제목은 무엇인가?''에서는 주민의 절반이 항상 거짓말을 하는 좀비이고 나머지 절반은 항상 참말을 하는 인간인 가상의 섬(혹은 아이티 섬^[5]) 이야기가 나온다. 이 섬의 주민들은 영어를 완벽하게 이해하지만, 고유의 언어 외에는 사용하면 안 된다는 금기 때문에 '예' 또는 '아니오' 질문에 'Bal'과 'Da'로만 대답한다. 문제는 어느 단어가 '예'이고 어느 단어가 '아니오'인지 알 수 없다는 점이다.^[5]^[15] 또한 ''셰헤라자데의 수수께끼''에도 다른 관련된 퍼즐들이 실려 있다.^[1]^[6]^[16]^[17]

컴퓨터 과학자 존 매카시는 'da'와 'ja'의 의미를 알 수 없다는 설정을 추가하여 퍼즐의 난이도를 높였다고 알려져 있다.^[1]^[16]

이러한 유형의 퍼즐은 1986년 판타지 영화 ''라비린스''에 등장하면서 대중적으로 알려졌다. 영화에서는 두 개의 문 앞에 각각 보초가 서 있는데, 한 명은 항상 참말을 하고 다른 한 명은 항상 거짓말을 한다. 문 하나는 성으로 통하고 다른 하나는 '확실한 죽음'으로 이어진다. 퍼즐은 보초 중 한 명에게 단 한 번의 예/아니오 질문을 하여 성으로 통하는 문을 알아내는 것이다. 영화에서 주인공이 사용한 질문은 "그[다른 보초]가 이 문이 성으로 이어진다고 말할까요?"였다.^[1]^[6]^[17]

3. 전제

이 퍼즐에는 세 명의 신이 등장한다. 각각의 신은 '참', '거짓', '랜덤' 중 하나의 정체를 가지고 있다.

참 (True): 항상 참말만 한다.
거짓 (False): 항상 거짓말만 한다.
랜덤 (Random): 무작위로 참말 또는 거짓말을 한다.

질문자는 이 세 신에게 총 세 번의 예·아니오 질문만을 할 수 있다. 각 질문은 한 명의 신에게만 해야 한다. 질문자의 목표는 세 번의 질문을 통해 세 신의 정체('참', '거짓', '랜덤')를 모두 알아내는 것이다.

신들은 질문자의 언어를 완벽하게 이해하지만, 대답은 오직 자신들의 언어인 'da'와 'ja' 두 단어만을 사용한다. 문제는 질문자가 'da'와 'ja' 중 어느 것이 '예'를 의미하고 어느 것이 '아니오'를 의미하는지 모른다는 점이다.

4. 풀이

불로스는 퍼즐을 소개한 같은 글에서 해답을 제시했다. "처음으로 할 일은 '랜덤'이 아니라고 확신할 수 있는 신을 찾아내는 것이다. 그러면 그는 '참' 아니면 '거짓'이다."^[22]^[13] 다양한 질문으로 이를 해결할 수 있으며, 초기 전략 중 하나는 복잡한 논리적 연결사(예: 논리적 쌍조건문)를 질문에 이용하는 것이다.^[1]

이후 로버츠(2001)와 라번과 라번(2008)은 반사실 조건문을 이용하여 퍼즐의 해를 더 단순화할 수 있음을 발견했다.^[23]^[24]^[1]^[7]^[16]^[18] 이 해법의 핵심은, 임의의 예/아니오 질문 Q에 대해서 '참' 또는 '거짓' 신에게 "만약 당신에게 Q를 물으면 당신은 'ja'라고 대답하겠습니까?"와 같은 형식의 질문을 활용하는 것이다.^[23]^[24] 이 질문 형식을 사용하면, 질문받은 신의 종류('참' 또는 '거짓')나 사용하는 언어('ja'/'da'의 의미)에 관계없이, 답변('ja' 또는 'da')을 통해 원래 질문 Q에 대한 실제 답('예' 또는 '아니오')을 알아낼 수 있다.

이러한 질문 전략들을 통해 단계적으로 신들의 정체를 밝혀나갈 수 있다. 자세한 풀이 과정과 논리적 증명은 하위 섹션에서 다룬다.

4. 1. 반사실적 조건문을 이용한 풀이

로버츠(2001)와 라번과 라번(2008)은 각각 독립적으로 반사실 조건문을 사용하여 퍼즐의 해를 단순화할 수 있음을 발견했다.^[16]^[18] 이 해법의 핵심은 어떤 예/아니오 질문 Q에 대해, 참 또는 거짓 신에게 다음과 같은 질문을 하는 것이다.

: 만약 내가 당신에게 Q를 묻는다면, 당신은 'ja'라고 말할 것입니까?^[23]^[24]

이 질문에 대한 대답은 Q에 대한 진실된 답이 '예'라면 'ja'이고, '아니오'라면 'da'이다.^[23]^[24] 질문받은 신이 참이든 거짓이든, 'ja'와 'da'가 각각 '예'와 '아니오' 중 무엇을 의미하든 상관없이 이 결과는 동일하다. 그 이유는 다음의 8가지 경우를 통해 알 수 있다.

'''ja'가 '예'이고 'da'가 '아니오'를 뜻한다고 가정하자.'''
# '참'에게 질문했고 'ja'라는 대답을 들었다면, 그는 참말을 하므로 Q에 대한 진실된 답은 'ja', 즉 '예'이다.
# '참'에게 질문했고 'da'라는 대답을 들었다면, 그는 참말을 하므로 Q에 대한 진실된 답은 'da', 즉 '아니오'이다.
# '거짓'에게 질문했고 'ja'라는 대답을 들었다면, 그는 거짓말을 하므로 만약 Q를 물었다면 'da'라고 답했을 것이다. 그는 거짓말쟁이이므로 Q에 대한 진실된 답은 'ja', 즉 '예'이다.
# '거짓'에게 질문했고 'da'라는 대답을 들었다면, 그는 거짓말을 하므로 만약 Q를 물었다면 'ja'라고 답했을 것이다. 그는 거짓말쟁이이므로 Q에 대한 진실된 답은 'da', 즉 '아니오'이다.

'''ja'가 '아니오'이고 'da'가 '예'를 뜻한다고 가정하자.'''
# '참'에게 질문했고 'ja'라는 대답을 들었다면, 그는 참말을 하므로 Q에 대한 진실된 답은 'da', 즉 '예'이다.
# '참'에게 질문했고 'da'라는 대답을 들었다면, 그는 참말을 하므로 Q에 대한 진실된 답은 'ja', 즉 '아니오'이다.
# '거짓'에게 질문했고 'ja'라는 대답을 들었다면, 그는 거짓말을 하므로 만약 Q를 물었다면 실제로 'ja'라고 답했을 것이다. 그는 거짓말쟁이이므로 Q에 대한 진실된 답은 'da', 즉 '예'이다.
# '거짓'에게 질문했고 'da'라는 대답을 들었다면, 그는 거짓말을 하므로 만약 Q를 물었다면 'da'라고 답했을 것이다. 그는 거짓말쟁이이므로 Q에 대한 진실된 답은 'ja', 즉 '아니오'이다.

이 사실(라번과 라번은 이를 '내장 질문 보조정리(embedded question lemma)'라고 부름)을 이용하여 다음과 같은 세 질문으로 퍼즐을 풀 수 있다.^[16]

# '''Q1:''' 신 B에게 "만약 내가 당신에게 'A가 랜덤인가요?'라고 물으면 'ja'라고 대답하겠습니까?" 라고 묻는다.

#* 만약 B가 'ja'라고 대답한다면, B가 '랜덤'이거나 (무작위로 대답) 또는 B가 '랜덤'이 아니고 A가 실제로 '랜덤'이라는 의미이다. 어느 경우든 C는 '랜덤'이 아니다.

#* 만약 B가 'da'라고 대답한다면, B가 '랜덤'이거나 (무작위로 대답) 또는 B가 '랜덤'이 아니고 A가 '랜덤'이 아니라는 의미이다. 어느 경우든 A는 '랜덤'이 아니다.

#* 이 질문을 통해 확실히 '랜덤'이 아닌 신(A 또는 C)을 특정할 수 있다.

# '''Q2:''' 앞서 '랜덤'이 아님이 밝혀진 신(A 또는 C)에게 가서 "만약 내가 당신에게 '당신은 거짓인가요?'라고 물으면 'ja'라고 대답하겠습니까?"라고 묻는다.

#* 그는 '랜덤'이 아니므로, 'ja'라는 대답은 그가 '거짓'임을 나타내고, 'da'라는 대답은 그가 참임을 나타낸다.

#* 이 질문을 통해 특정된 신의 정체('참' 또는 '거짓')를 알 수 있다.

# '''Q3:''' 같은 신에게 "만약 내가 당신에게 'B가 랜덤인가요?'라고 물으면 'ja'라고 대답하겠습니까?"라고 묻는다.

#* 대답이 'ja'이면 B가 '랜덤'이다.

#* 대답이 'da'이면 아직 묻지 않은 다른 신(A 또는 C 중 남은 신)이 '랜덤'이다.

#* B의 정체를 알게 되면, 나머지 한 신의 정체는 소거법으로 결정된다.

다음 표는 세 질문 전략에 따른 16가지 가능한 시나리오와 결과를 요약한 것이다.

사례		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
A		참	참		거짓	랜덤	거짓		랜덤	참	참		거짓	랜덤	거짓		랜덤
B		거짓	랜덤		참	참	랜덤		거짓	거짓	랜덤		참	참	랜덤		거짓
C		랜덤	거짓		랜덤	거짓	참		참	랜덤	거짓		랜덤	거짓	참		참
Da		예	예		예	예	예		예	아니오	아니오		아니오	아니오	아니오		아니오
Ja		아니오	아니오		아니오	아니오	아니오		아니오	예	예		예	예	예		예
A가 실제로 랜덤인가?		아니오	아니오		아니오	예	아니오		예	아니오	아니오		아니오	예	아니오		예
B가 "A는 랜덤인가?"에 어떻게 대답할 것인가?	예/아니오	예	둘 다		아니오	예	둘 다		아니오	예	둘 다		아니오	예	둘 다		아니오
B가 "A는 랜덤인가?"에 어떻게 대답할 것인가?	신의 언어	Da	둘 다		Ja	Da	둘 다		Ja	Ja	둘 다		Da	Ja	둘 다		Da
Q1: B의 응답 "만약 내가 당신에게 A가 랜덤인가라고 질문한다면, 당신은 ja라고 말하겠습니까?"	예/아니오	예	둘 다		예	아니오	둘 다		아니오	아니오	둘 다		아니오	예	둘 다		예
	신의 언어	Da	둘 다		Da	Ja	둘 다		Ja	Da	둘 다		Da	Ja	둘 다		Ja
	신의 언어	Da	Da	Ja	Da	Ja	Da	Ja	Ja	Da	Da	Ja	Da	Ja	Da	Ja	Ja
따라서, __ (이하 X)는 랜덤이 아님		A	A	C	A	C	A	C	C	A	A	C	A	C	A	C	C
X가 실제로 거짓인가?		아니오	아니오	예	예	예	예	아니오	아니오	아니오	아니오	예	예	예	예	아니오	아니오
"당신은 거짓인가?"에서 X의 답변 방법	예/아니오	아니오	아니오	아니오	아니오	아니오	아니오	아니오	아니오	아니오	아니오	아니오	아니오	아니오	아니오	아니오	아니오
"당신은 거짓인가?"에서 X의 답변 방법	신의 언어	Ja	Ja	Ja	Ja	Ja	Ja	Ja	Ja	Da	Da	Da	Da	Da	Da	Da	Da
Q2: X의 응답 만약 "당신은 거짓인가?"라고 묻는다면, 답변은 ja입니까?	예/아니오	예	예	아니오	아니오	아니오	아니오	예	예	아니오	아니오	예	예	예	예	아니오	아니오
Q2: X의 응답 만약 "당신은 거짓인가?"라고 묻는다면, 답변은 ja입니까?	신의 언어	Da	Da	Ja	Ja	Ja	Ja	Da	Da	Da	Da	Ja	Ja	Ja	Ja	Da	Da
따라서 X는 __.		참	참	거짓	거짓	거짓	거짓	참	참	참	참	거짓	거짓	거짓	거짓	참	참
B가 실제로 랜덤인가?		아니오	예		아니오	아니오	예		아니오	아니오	예		아니오	아니오	예		아니오
"B는 랜덤인가?"에서 X의 답변 방법	예/아니오	아니오	예	아니오	예	예	아니오	예	아니오	아니오	예	아니오	예	예	아니오	예	아니오
"B는 랜덤인가?"에서 X의 답변 방법	신의 언어	Ja	Da	Ja	Da	Da	Ja	Da	Ja	Da	Ja	Da	Ja	Ja	Da	Ja	Da
Q3: X의 응답 "만약 내가 당신에게 B는 랜덤인가?라고 묻는다면, 당신은 ja라고 말하겠습니까?"	예/아니오	예	아니오	아니오	예	예	아니오	아니오	예	아니오	예	예	아니오	아니오	예	예	아니오
Q3: X의 응답 "만약 내가 당신에게 B는 랜덤인가?라고 묻는다면, 당신은 ja라고 말하겠습니까?"	신의 언어	Da	Ja	Ja	Da	Da	Ja	Ja	Da	Da	Ja	Ja	Da	Da	Ja	Ja	Da
따라서 __가 랜덤.		C	B	B	C	A	B	B	A	C	B	B	C	A	B	B	A
소거법에 의해, 남은 신과 속성	남은 신	B	C	A	B	B	C	A	B	B	C	A	B	B	C	A	B
소거법에 의해, 남은 신과 속성	속성	거짓	거짓	참	참	참	참	거짓	거짓	거짓	거짓	참	참	참	참	거짓	거짓

4. 2. 구체적인 풀이 단계

불로스는 퍼즐을 소개한 같은 글에서 해답을 제시했다. 그는 "처음으로 할 일은 '랜덤'이 아니라고 확신할 수 있는 신을 찾아내는 것이다. 그러면 그는 '참' 아니면 '거짓'이다."라고 말했다.^[22]^[13] 다양한 질문으로 이것을 해낼 수 있는데, 한 가지 전략은 복잡한 논리적 연결, 예를 들어 논리적 쌍조건문을 이용하는 것이다.

불로스가 제시한 질문 중 하나는 신 A에게 다음과 같이 묻는 것이다.^[13]

'da'가 '예'를 뜻하는 것과 당신이 '참'인 것과 B가 '랜덤'인 것은 모두 동치입니까?

혹은 같은 의미로:

"당신은 '거짓'이다", "'ja'는 '예'를 뜻한다", "B는 '랜덤'이다"의 세 문장 중 참인 것이 홀수개입니까?

이후 로버츠(2001)와 라번 등(2008)은 반사실 조건문을 이용하여 퍼즐의 해를 더 단순화할 수 있음을 발견했다.^[23]^[24]^[1]^[7]^[16]^[18] 이 해법의 핵심은, 임의의 예/아니오 질문 Q에 대해, '참' 또는 '거짓' 신에게 다음과 같은 형식의 질문을 하는 것이다.

"만약 당신에게 Q를 질문한다면, 당신은 'ja'라고 말하겠습니까?"

이 질문의 중요한 특징은, 질문을 받은 신이 '참'이든 '거짓'이든, 그리고 'ja'와 'da'가 각각 '예'와 '아니오' 중 무엇을 의미하든 관계없이, Q에 대한 실제 정답이 '예'라면 항상 'ja'라고 답하고, Q에 대한 실제 정답이 '아니오'라면 항상 'da'라고 답한다는 점이다. 라번 등은 이 결과를 '내장 질문 보조 정리'(embedded question lemma)라고 불렀다.^[1]^[18]

이것이 왜 작동하는지는 다음 8가지 가능한 경우를 분석해보면 알 수 있다.

'''가정 1: 'ja'가 '예'를, 'da'가 '아니오'를 의미하는 경우'''
# '참'에게 질문했고 'ja'('예')라고 답했다면, 그는 참말을 하므로 Q에 대한 실제 답은 '예'이다.
# '참'에게 질문했고 'da'('아니오')라고 답했다면, 그는 참말을 하므로 Q에 대한 실제 답은 '아니오'이다.
# '거짓'에게 질문했고 'ja'('예')라고 답했다면, 그는 거짓말을 하므로 만약 Q를 직접 물었다면 'da'('아니오')라고 답했을 것이다. 그가 거짓말쟁이이므로 Q에 대한 실제 답은 'ja', 즉 '예'이다.
# '거짓'에게 질문했고 'da'('아니오')라고 답했다면, 그는 거짓말을 하므로 만약 Q를 직접 물었다면 'ja'('예')라고 답했을 것이다. 그가 거짓말쟁이이므로 Q에 대한 실제 답은 'da', 즉 '아니오'이다.

'''가정 2: 'ja'가 '아니오'를, 'da'가 '예'를 의미하는 경우'''
# '참'에게 질문했고 'ja'('아니오')라고 답했다면, 그는 참말을 하므로 Q에 대한 실제 답은 'da', 즉 '예'이다.
# '참'에게 질문했고 'da'('예')라고 답했다면, 그는 참말을 하므로 Q에 대한 실제 답은 'ja', 즉 '아니오'이다.
# '거짓'에게 질문했고 'ja'('아니오')라고 답했다면, 그는 거짓말을 하므로 만약 Q를 직접 물었다면 'ja'('아니오')라고 답했을 것이다. 그가 거짓말쟁이이므로 Q에 대한 실제 답은 'da', 즉 '예'이다.
# '거짓'에게 질문했고 'da'('예')라고 답했다면, 그는 거짓말을 하므로 만약 Q를 직접 물었다면 'da'('예')라고 답했을 것이다. 그가 거짓말쟁이이므로 Q에 대한 실제 답은 'ja', 즉 '아니오'이다.

결론적으로, 어떤 경우든 "만약 당신에게 Q를 질문한다면, 당신은 'ja'라고 말하겠습니까?"라는 질문에 대해 'ja'라는 답변을 들으면 Q의 실제 답은 '예'이고, 'da'라는 답변을 들으면 Q의 실제 답은 '아니오'임을 알 수 있다.

이 원리를 이용하여 다음과 같이 세 번의 질문으로 퍼즐을 풀 수 있다.^[22]^[1]^[16]

질문 1: '랜덤'이 아닌 신 식별하기
신 B에게 묻는다: "만약 내가 당신에게 'A는 랜덤입니까?'라고 질문한다면, 당신은 'ja'라고 말하겠습니까?"
만약 B가 'ja'라고 답한다면:
B가 '랜덤'이고 무작위로 답했을 수 있다.
B가 '랜덤'이 아니고, 위 원리에 따라 'A는 랜덤입니까?'의 실제 답이 '예'임을 의미한다. 즉, A가 '랜덤'이다.
두 경우 모두, C는 '랜덤'이 아니다.
만약 B가 'da'라고 답한다면:
B가 '랜덤'이고 무작위로 답했을 수 있다.
B가 '랜덤'이 아니고, 위 원리에 따라 'A는 랜덤입니까?'의 실제 답이 '아니오'임을 의미한다. 즉, A가 '랜덤'이 아니다.
두 경우 모두, A는 '랜덤'이 아니다.
이 질문을 통해 우리는 A 또는 C 중 누가 '랜덤'이 아닌지 확실히 알 수 있다. 이 신을 X라고 하자.

질문 2: X의 정체('참' 또는 '거짓') 파악하기
질문 1에서 '랜덤'이 아니라고 밝혀진 신 X에게 묻는다: "만약 내가 당신에게 '당신은 거짓입니까?'라고 질문한다면, 당신은 'ja'라고 말하겠습니까?" (또는 더 간단히 "만약 내가 당신에게 ''da'는 '예'를 의미합니까?'라고 질문한다면, 당신은 'ja'라고 말하겠습니까?")
X는 '랜덤'이 아니므로, 위 원리가 적용된다.
만약 X가 'ja'라고 답한다면: '당신은 거짓입니까?'의 실제 답이 '예'라는 뜻이므로, X는 '거짓'이다.
만약 X가 'da'라고 답한다면: '당신은 거짓입니까?'의 실제 답이 '아니오'라는 뜻이므로, X는 '참'이다.

질문 3: 나머지 신들의 정체 파악하기
여전히 신 X에게 묻는다: "만약 내가 당신에게 'B는 랜덤입니까?'라고 질문한다면, 당신은 'ja'라고 말하겠습니까?"
만약 X가 'ja'라고 답한다면: 'B는 랜덤입니까?'의 실제 답이 '예'라는 뜻이므로, B는 '랜덤'이다. 그러면 남은 신(A 또는 C 중 X가 아닌 신)은 X의 정체('참' 또는 '거짓')와 반대되는 정체를 가진다.
만약 X가 'da'라고 답한다면: 'B는 랜덤입니까?'의 실제 답이 '아니오'라는 뜻이므로, B는 '랜덤'이 아니다. 이 경우, 아직 질문하지 않은 다른 신(A 또는 C 중 X가 아닌 신)이 '랜덤'이다. B의 정체는 X의 정체와 반대되는 정체('참' 또는 '거짓')를 가진다.

이 세 질문을 통해 모든 신의 정체('참', '거짓', '랜덤')를 완전히 파악할 수 있다.

아래 표는 16가지 가능한 모든 경우의 수에 대해 위 3단계 질문 절차를 적용했을 때의 결과와 최종적인 신들의 정체 판별 과정을 보여준다. (신의 답변이 무작위일 경우 '둘 다'로 표기됨)

케이스		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
신 A		참	참		거짓	랜덤	거짓		랜덤	참	참		거짓	랜덤	거짓		랜덤
신 B		거짓	랜덤		참	참	랜덤		거짓	거짓	랜덤		참	참	랜덤		거짓
신 C		랜덤	거짓		랜덤	거짓	참		참	랜덤	거짓		랜덤	거짓	참		참
Da의 의미		예	예		예	예	예		예	아니오	아니오		아니오	아니오	아니오		아니오
Ja의 의미		아니오	아니오		아니오	아니오	아니오		아니오	예	예		예	예	예		예
A는 실제로 랜덤인가?		아니오	아니오		아니오	예	아니오		예	아니오	아니오		아니오	예	아니오		예
질문 1에서 B의 답변 "만약 내가 당신에게 A는 랜덤인가?라고 질문한다면, 당신은 ja라고 말하겠습니까?"	예/아니오	예	둘 다		예	아니오	둘 다		아니오	아니오	둘 다		아니오	예	둘 다		예
	신의 말	Da	둘 다		Da	Ja	둘 다		Ja	Da	둘 다		Da	Ja	둘 다		Ja
	신의 말	Da	Da	Ja	Da	Ja	Da	Ja	Ja	Da	Da	Ja	Da	Ja	Da	Ja	Ja
따라서, __(이하 X)는 비랜덤		A	A	C	A	C	A	C	C	A	A	C	A	C	A	C	C
X는 실제로 거짓인가?		아니오	아니오	예	예	예	예	아니오	아니오	아니오	아니오	예	예	예	예	아니오	아니오
질문 2에서 X의 답변 "만약 내가 당신에게 당신은 거짓인가?라고 질문한다면, 당신은 ja라고 말하겠습니까?"	예/아니오	예	예	아니오	아니오	아니오	아니오	예	예	아니오	아니오	예	예	예	예	아니오	아니오
	신의 말	Da	Da	Ja	Ja	Ja	Ja	Da	Da	Da	Da	Ja	Ja	Ja	Ja	Da	Da
따라서 X는 __.		참	참	거짓	거짓	거짓	거짓	참	참	참	참	거짓	거짓	거짓	거짓	참	참
B는 실제로 랜덤인가?		아니오	예		아니오	아니오	예		아니오	아니오	예		아니오	아니오	예		아니오
질문 3에서 X의 답변 "만약 내가 당신에게 B는 랜덤인가?라고 질문한다면, 당신은 ja라고 말하겠습니까?"	예/아니오	예	아니오	아니오	예	예	아니오	아니오	예	아니오	예	예	아니오	아니오	예	예	아니오
	신의 말	Da	Ja	Ja	Da	Da	Ja	Ja	Da	Da	Ja	Ja	Da	Da	Ja	Ja	Da
따라서 __가 랜덤.		C	B	B	C	A	B	B	A	C	B	B	C	A	B	B	A
소거법에 따른 나머지 신과 정체	남은 신	B	C	A	B	B	C	A	B	B	C	A	B	B	C	A	B
소거법에 따른 나머지 신과 정체	정체	거짓	거짓	참	참	참	참	거짓	거짓	거짓	거짓	참	참	참	참	거짓	거짓

5. '랜덤'의 행동에 대한 다양한 해석

불로스는 '랜덤'의 행동을 다음과 같이 설명한다.^[1]^[16]

'랜덤'이 참말을 할지 거짓말을 할지는 그의 머릿속에서 던진 동전의 앞뒷면에 따라 결정되는 것으로 생각할 수 있다. 앞면이라면, 참말을 한다. 뒷면이라면 거짓말을 할 것이다.

이 설명은 '랜덤'이 각 질문마다 새로 동전을 던지는지, 아니면 질문 세션 전체에 걸쳐 한 번 던진 결과(참말쟁이 또는 거짓말쟁이)를 유지하는지 명확히 하지 않는다.^[1]^[16] 이 모호성은 '랜덤'을 어떻게 다룰지에 대한 여러 해석을 낳았다.

만약 '랜덤'이 세션 전체에 걸쳐 지속되는 단일 무작위 선택(즉, 세션 동안 참말쟁이 또는 거짓말쟁이 중 하나의 역할을 고정적으로 수행)을 한다고 해석할 경우, 라번과 라번(Rabern and Rabern, 2008)은 '랜덤'에게서도 유용한 답변을 얻을 수 있음을 보여주었다.^[1]^[16] 이는 반사실적 조건문을 이용한 특정 질문 방식이 답변자('랜덤' 포함)가 참말쟁이든 거짓말쟁이든 상관없이 원래 질문(Q)에 대한 진실된 답('ja' 또는 'da')을 밝히도록 설계되었기 때문이다.

하지만 '랜덤'의 행동에 대한 다른 해석도 가능하다. 예를 들어, '랜덤'이 머릿속 동전 던지기로 참/거짓 상태를 정한 뒤 질문 전체에 답하지만, 반사실적 조건문 질문을 받았을 때는 그 질문이 가정하는 상황(예: "만약 내가 당신에게 Q를 묻는다면...")이 아닌, 질문을 받는 시점의 실제 참/거짓 상태를 기준으로 답한다고 해석할 수도 있다. 이 경우 반사실적 조건문 질문은 '랜덤'에게 무용지물이 된다. 이 문제를 피하기 위해 질문을 "내가 당신의 ''현재 정신 상태''에서 Q를 묻는다면, 당신은 ''ja''라고 말하겠습니까?"^[8]^[16] 와 같이 수정하는 방법이 제안되었다. 이 질문은 '랜덤'에게 현재의 참말쟁이 또는 거짓말쟁이 상태 중 하나를 강제로 선택하게 하여 의미 있는 답변을 얻으려는 시도이다. 그러나 이 접근법은 '랜덤'이 질문에 대한 답을 결정하기 전에 자신의 참/거짓 상태를 먼저 확정한다고 가정하는데, 이는 퍼즐 원문이나 불로스의 설명에는 명시되지 않은 가정이다.^[16]

불로스가 제시한 원래 문제와 설명("동전이 앞면으로 나오면 진실을 말하고, 뒷면으로 나오면 거짓을 말한다")^[16]의 틀 안에서, 추가적인 가정 없이 진실된 답변을 얻기 위한 또 다른 질문 형식도 제안되었다.

"만약 내가 당신에게 Q를 묻는다면, 그리고 만약 당신이 이 질문에 대답하는 것처럼 정직하게 대답했었더라면, 당신은 ja라고 말하겠습니까?"

이 질문은 '랜덤'이 질문에 답하는 순간에는 정직하게(참말) 또는 부정직하게(거짓말) 행동한다는, 불로스의 설명에 이미 포함된 가정만을 이용한다.^[16]

한편, 라번과 라번(2008)은 퍼즐의 난이도를 높이고 '랜덤'을 진정한 의미의 무작위적 존재로 만들기 위해, 불로스의 설명을 다음과 같이 수정할 것을 제안하기도 했다.^[16]

'랜덤'이 ''ja'' 또는 ''da''를 말하는 것은 그의 머릿속에 숨겨진 동전 던지기에 따라 생각해야 한다: 동전이 앞면이라면, ''ja''라고 말하고, 뒷면이라면 그는 ''da''라고 말한다.

이 수정안은 '랜덤'이 참/거짓 상태를 무작위로 정하는 것이 아니라, 답변 자체('ja' 또는 'da')를 무작위로 선택하도록 변경한다. 이 규칙 하에서는 퍼즐을 풀기 위해 더욱 신중하고 복잡한 질문 전략이 필요하게 된다.^[16]

6. 신의 머리 폭발

B. Rabern과 L. Rabern은 "가장 어려운 논리 퍼즐에 대한 간단한 해결책"이라는 논문에서^[1]^[22]^[16], 신들이 역설적인 질문에 직면했을 때 'ja'나 'da'로 대답하지 못하고 침묵하는 경우, 즉 "머리가 폭발하는" 상황을 고려한 퍼즐 변형을 제시했다. 예를 들어, '참'에게 "당신은 이 질문에 '아니오'라는 뜻을 가진 단어로 대답할 것입니까?"라고 물으면, '참'은 진실을 말해야 하므로 'ja' 또는 'da' 어느 쪽으로도 대답할 수 없게 된다. 논문에서는 이를 "머리 폭발"이라고 표현하며, 오류가 있을 수 없는 신들이 이런 상황에 처하면 머리가 폭발하는 것 외에는 선택지가 없다고 설명한다.

이 "머리 폭발" 가능성을 인정하면, 원래 3번의 질문이 필요했던 퍼즐을 단 2번의 질문만으로 해결할 수 있는 새로운 방법이 열린다. 저자들은 이를 설명하기 위해 다음과 같은 더 간단한 퍼즐을 2개의 질문으로 해결하는 방법을 보여준다.

세 신 A, B, C의 이름은 각각 제피르, 에우로스, 아이올로스인데, 누가 누구인지는 모른다. 각 신은 항상 참말만을 한다. 이제 예/아니오 질문을 해서 A, B, C의 정체를 밝혀내야 한다. 각 질문은 한 번에 한 명의 신에게만 할 수 있으며, 신들은 영어를 이해하고 영어로 대답한다.

이 퍼즐은 보통 3번의 질문으로 해결할 수 있지만, 2번의 질문으로 해결하기 위해 다음과 같은 보조정리를 사용한다.

'''조절된 거짓말쟁이 보조정리 (Tempered Liar Lemma)'''

만약 신 A에게 "{[(당신은 이 질문에 '아니오'라고 대답할 것이다) '''그리고''' (B는 제피르이다)] '''또는''' (B는 에우로스이다)}인 것이 사실입니까?" 라고 질문한다고 가정하자.

만약 A가 '예'라고 대답하면, B는 에우로스이다.
만약 A가 '아니오'라고 대답하면, B는 아이올로스이다.
만약 A의 머리가 폭발한다면 (대답하지 못한다면), B는 제피르이다.

따라서 단 한 번의 질문으로 B의 정체를 알아낼 수 있다.

이 보조정리를 사용하면 위 퍼즐을 두 질문만으로 해결하는 것이 간단해진다. Rabern과 Rabern(2008)은 비슷한 방식(거짓말쟁이 역설을 이용한 질문)을 사용하여 원래의 "가장 어려운 논리 퍼즐" 역시 2번의 질문으로 해결할 수 있음을 보였다.

우즈키아노(Uzquiano, 2010)는 이러한 기법을 사용하여 수정된 퍼즐(랜덤 신이 정말 무작위로 대답하는 경우)에 대한 2개 질문 해결책을 제시했다.^[9]^[10]^[19]^[20] 이 2개 질문 해결책들은 '참'이나 '거짓' 신이 특정 질문에는 대답할 수 없다는 점을 이용한다. 예를 들어 다음과 같은 질문이 있다.

: 당신은 '랜덤'이 '두샨베가 키르기스스탄에 있습니까?'라는 질문에 대답하는 것과 똑같이 대답하겠습니까?

수정된 퍼즐에서 '랜덤'은 정말 무작위로 대답하기 때문에, '참'이나 '거짓'은 '랜덤'이 'ja'라고 할지 'da'라고 할지 예측할 수 없다. 따라서 이 질문에 진실을 말하거나 거짓말을 할 수 없어 침묵하게 된다(머리 폭발). 반면, 무작위로 대답하는 '랜덤'은 그냥 'ja'나 'da' 중 하나를 말할 것이다. 우즈키아노는 이러한 비대칭성을 이용했다.

만약 신들이 '랜덤'의 무작위 답변조차 미리 알 수 있는 예언 능력이 있다고 가정한다면^[19], Rabern 등(2008)이 사용한 것과 유사한 자기 참조 질문을 통해 여전히 2개 질문 해결책이 가능하다.

: 당신은 이 질문에 'da'라고 대답할 것인지에 대한 질문에 'ja'라고 대답하겠습니까?

이 질문 역시 '참'과 '거짓'은 대답할 수 없다. 자신이 해야 할 대답('ja' 또는 'da')과 실제 대답이 모순되기 때문이다. 따라서 머리가 폭발하지만, '랜덤'은 무작위로 'ja'나 'da' 중 하나를 말할 것이다. 우즈키아노(2010)는 이 비대칭성을 이용한 2개 질문 해결책도 제시했다.^[19] ^[20]

그러나 우즈키아노가 제안한 또 다른 수정안, 즉 '랜덤' 신도 'ja', 'da' 외에 침묵(머리 폭발)할 수 있도록 허용한 퍼즐의 경우에는 이러한 비대칭성이 사라져 3개 미만의 질문으로는 해결할 수 없게 된다.^[11]^[21]

참조

_[1] 논문 The hardest logic puzzle ever http://www.hcs.harva[...]
_[2] 웹사이트 The Hardest Logic Puzzle Ever? (with Answer) https://puzzleness.c[...] Puzzleness 2021-04-14
_[3] 문서 Da means yes in Russian language, ja means yes in German language.
_[4] 문서 Note that the Random god in Boolos' puzzle is a god who acts randomly as either a truth-teller or a liar. This is different from a god who answers 'yes' or 'no' randomly. One usual trick in solving many logic puzzles is to design a (perhaps composite) question that forces both a truth-teller and a liar to answer 'yes'. For such a question, a person who randomly chooses to be a truth-teller or a liar is still forced to answer 'yes', but a person who answers randomly may answer 'yes' or 'no'.
_[5] 서적 What is the Name of This Book? Prentice Hall
_[6] 서적 The Riddle of Scheherazade A. A. Knopf, Inc
_[7] 논문 Some Thoughts about the Hardest Logic Puzzle Ever
_[8] 논문 A simple solution to the hardest logic puzzle ever https://www.pure.ed.[...]
_[9] 논문 How to solve the hardest logic puzzle ever in two questions
_[10] 간행물 In defense of the two question solution to the hardest logic puzzle ever https://dl.dropbox.c[...] dropbox.com
_[11] 논문 Why the Hardest Logic Puzzle Ever Cannot Be Solved in Less than Three Questions http://philsci-archi[...]
_[12] 간행물 The Hardest Logic Puzzle Ever https://doi.org/10.5[...]
_[13] 논문 The hardest logic puzzle ever http://www.hcs.harva[...]
_[14] 문서 ブーロスのパズルにおけるランダム神は、真実の証人か嘘つきのどちらかとして、ランダムに行動する神であることに注意しなければならない。これは無作為に「yes」または「no」と答える神とは異なる。多くの論理パズルを解決する一般的手口は、真実の証人と嘘つきの両方に「yes」と答えさせる質問（恐らく複合した）を設計することにある。そういった質問に対し、真実の証人か嘘つきかをランダムに選択した者は依然として「yes」と答えざるをえないが、無作為に答える人は「yes」または「no」と答えることがある。
_[15] 서적 What is the Name of This Book? Prentice Hall
_[16] 간행물 A simple solution to the hardest logic puzzle ever
_[17] 서적 The Riddle of Scheherazade A. A. Knopf, Inc
_[18] 논문 Some Thoughts about the Hardest Logic Puzzle Ever
_[19] 논문 How to solve the hardest logic puzzle ever in two questions
_[20] 간행물 In defense of the two question solution to the hardest logic puzzle ever dropbox.com
_[21] 논문 Why the Hardest Logic Puzzle Ever Cannot Be Solved in Less than Three Questions
_[22] 간행물 The Hardest Logic Puzzle Ever
_[23] 간행물 A simple solution to the hardest logic puzzle ever 2008-04
_[24] 간행물 Some thoughts about the hardest logic puzzle ever 2001-12

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com