최근 수정 시각 : 2024-12-10 07:29:31

가장 어려운 논리 퍼즐


TED의 설명영상, 한국어 자막을 지원한다.

1. 개요2. 문제3. 해답
3.1. 질문의 방식3.2. 누가 랜덤이 아닌지 알아내기3.3. 랜덤이 아닌 신에게 질문하기3.4. 다른 풀이
4. 특이한 풀이: 머리 폭발

1. 개요

가장 어려운 논리 퍼즐(The Hardest Logic Puzzle Ever), 비 공식적으로는 세명의 신 수수께끼라고도 불린다.

천사와 악마, 기사와 건달류의 문제를 저서 <이 책의 제목은 무엇인가?>를 통해서 발표한 적 있던 논리학자 레이먼드 스멀리안(Raymond Smullyan)이 처음 아이디어를 고안했으며, John McCarthy가 수정을 거치고, 미국의 철학자이자 논리학자 조지 볼로스(George Boolos)가 이를 1996년 서적 The Harvard Review of Philosophy을 통해 발표한 논리 퍼즐이다.

2. 문제

세명의 신이 존재한다. 이들의 이름은 '트루(True)', '폴스(False)', '랜덤(Random)' 인데[1] 무엇이 누구의 이름인지는 모른다. '트루'는 언제나 진실을 하고 '폴스'는 언제나 거짓말을 한다. '랜덤'은 완전히 무작위로 진실을 말할 때도 있고 거짓을 말할 때도 있다. 목표는 맞다/아니다 로만 대답 가능한 질문을 단 3번만 하여 세 명의 신 모두 누가 어떤 이름인지를 알아내는 것이다.[2] 신들은 우리의 언어를 알아듣지만 그들의 대답은 '예' 혹은 '아니오'의 뜻을 지닌 그들의 언어 'da/ja' 두개로만 주어지는데[3], ja와 da중 어떤 단어가 '예'이고 어떤 단어가 '아니오'인지는 모른다.

3. 해답

3.1. 질문의 방식

우선은 ja와 da중 어느게 참이고 어느게 거짓 인지는 알 필요가 없다. "만약 제가 [질문] 이라고 묻는 다면, 당신의 대답은 ja (혹은 da) 인가요?" 라는 식으로 질문을 조건문(if)으로 제시하면 된다. 만약 상대가 트루 혹은 폴스일 경우, 여기서 내가 질문에서 제시한 단어와 같은 단어의 대답이 돌아온다면 그 질문에 대한 긍정이고, 반대로 질문에서 제시한 단어와 반대의 단어가 대답으로 돌아온다면 그 질문에 대한 부정이다.[4]

예를들어 "만약 제가 '2+2는 4인가'라고 묻는다면, 당신의 대답은 ja 인가요?"라고 질문했다고 치자.(이 때 연산은 10진법에서라고 하자. 일례로 만약 4진법이라면 2+2=10이 되어 2+2=4는 거짓이 되어버린다.)
  • 만약 ja가 '맞다'이고 da가 '아니다'라는 뜻일 경우
    • 질문한 상대가 '트루'일 경우: '2+2=4?'라고 질문할 경우 ja(참)이라 대답할테고, 그 질문에 대한 답이 ja 냐고 대답할 것이냐는 질문도 마찬가지로 문제없이 ja라고 대답할 것 이다.
    • 질문한 상대가 '폴스'일 경우: 폴스에게 '2+2=4?' 라고만 질문했다면 거짓말로 da(아니다) 라고 대답할 것 이다. '그 질문에 ja(맞다)라고 대답할 것 이냐?' 라는 질문에 폴스 입장에서 정직하게 대답하면 da(아니오)라고 대답해야한다. 하지만 '폴스'는 거짓말을 해야하니 사실이라고 해야한다. 따라서 ja 라고 답한다.
  • 만약 da가 '맞다'이고 ja가 '아니다'라는 뜻일 경우
    • 질문한 상대가 '트루'일 경우: 자신은 '2+2=4?'라는 질문에는 da(참) 이라고 대답할 것이기 때문에, 그 질문에 대한 답이 ja(아니다) 냐는 인간의 질문에는 ja(아니다) 라고 대답할 것 이다.
    • 질문한 상대가 '폴스'일 경우: 폴스는 '2+2=4?'라는 질문에는 거짓말로 ja(아니다) 라고 대답할 것 이기에, '그 질문에 대한 답이 ja(아니다) 인가?'라는 인간의 질문에는 만약 진실되게 말했다면 참(da) 이라고 하겠지만, 그 질문에서 마저 거짓말을 해야하니 최종적으로는 ja(아니다) 라고 할 것 이다.

반대로 질문에서 ja가 아닌 da를 제시해서 "만약 제가 '2+2는 4인가'라고 묻는다면, 당신의 대답은 da 인가요?" 일 경우도
  • 만약 da가 '맞다'이고 ja가 '아니다'라는 뜻일 경우
    • 질문한 상대가 '트루'일 경우: 자신은 '2+2=4?'라는 질문에는 da(참) 이라고 대답할 것이기 때문에, 그 질문에 대한 답이 da(맞다) 냐는 인간의 질문에도 da(맞다) 라고 대답할 것 이다.
    • 질문한 상대가 '폴스'일 경우: 폴스는 '2+2=4?'라는 질문에는 거짓말로 ja(아니다) 라고 대답할 것 이기에, '그 질문에 대한 답이 da(맞다) 인가?'라는 인간의 질문에는 만약 진실되게 말했다면 아니다(ja) 라고 하겠지만, 그 질문에서 마저 거짓말을 해야하니 최종적으로는 da(맞다) 라고 할 것 이다.
  • 만약 ja가 '맞다'이고 da가 '아니다'라는 뜻일 경우
    • 질문한 상대가 '트루'일 경우: '2+2=4?'라고 질문할 경우 ja(참)이라 대답할테고, 그 질문에 대한 답이 da(아니다) 냐고 대답할 것이냐는 질문에는 da(아니다)라고 대답할 것 이다.
    • 질문한 상대가 '폴스'일 경우: 폴스에게 '2+2=4?' 라고만 질문했다면 거짓말로 da(아니다) 라고 대답할 것 이다. 고로 '그 질문에 da(아니다)라고 대답할 것 이냐?' 라는건 폴스 입장에선 사실이지만, 이 질문에 대한 답도 거짓말을 해야하니 사실이 아니라고 해야한다. 따라서 '그 질문에 da라고 대답할 것 이냐'라는 질문에서는 부정인 da 라고 답한다.


여기에 추가해서 틀린 명제를 물었다고 하면.. "만약 제가 '2+2는 9인가'라고 묻는다면, 당신의 대답은 ja 인가요?"라고 질문했다고 치자.
  • 만약 ja가 '맞다'이고 da가 '아니다'라는 뜻일 경우
    • 질문한 상대가 '트루'일 경우: '2+2=9?'라고 질문할 경우 da(거짓)이라 대답할테고, 그 질문에 대한 답이 ja(참) 냐고 대답할 것이냐는 질문에는 참(ja)이라고 대답하지 않을 것이기에 반대로 da라고 대답할 것 이다.
    • 질문한 상대가 '폴스'일 경우: 폴스에게 '2+2=9?' 라고만 질문했다면 거짓말로 ja(참) 라고 대답할 것 이다. '그 질문에 ja(맞다)라고 대답할 것 이냐?' 라는 질문에는 반대로 거짓말 해야하기에 da라고 대답할 것 이다.
  • 만약 da가 '맞다'이고 ja가 '아니다'라는 뜻일 경우
    • 질문한 상대가 '트루'일 경우: 자신은 '2+2=9?'라는 질문의 답은 ja(아니오)이고, '그 질문에 대한 답이 ja(아니다) 냐'는 인간의 질문에는 아니다(ja)라고 대답해야 하는게 맞기에 da 라고 대답할 것이기에 이다.
    • 질문한 상대가 '폴스'일 경우: 폴스는 '2+2=9?'라는 질문에 대한 답변은 거짓말인 da(참) 라고 대답할 것이다. '그 질문에 대한 답이 ja(아니다) 인가?'라는 인간의 질문에는 실제로 자신은 '2+2=9는 da(참)'이라고 대답했으므로, 이 대답이 '아니오'인지 묻는 것에 대해 정직하게 답하면 아니오(ja)라고 해야 한다. 하지만 폴스는 거짓말을 해야하기에 이 질문에 da라고 대답할 것 이다.[5]


ja와 da중 어느게 예/아니오 인지 모르는 상태이며 질문한 상대가 트루인지 폴스인지도 모르는 상태지만 질문에서 ja를 제시하든 da를 제시하든, 어찌되었건 내가 질문에서 제시한 단어가 동일하게 대답에서 제시된다면 조건문으로 넣은 질문이 사실이라는 것, 질문에서 제시한 단어와 반대의 단어가 대답으로 돌아왔다면 조건문에 넣은 질문은 사실이 아니라는게 모든 경우의 수에서 동일하게 적용된다. 이는 긍정+긍정과, 부정+부정 모두 긍정이라는 논리학에 기반한다.

결론을 도출하기위해 설명하면 질문이"명제 A가 맞냐?라는 질문에 대한 너의 답은 B냐?" 일 경우, 명제 A는 '참일수도 있고 거짓일 수도 있으며', 답 B는 예/아니오 중 하나라고 하자. 만약 질문의 속 B가 답변의 B와 같아서 모두 '예'이거나 모두 '아니오'일 경우 명제 A는 참이다. 만약 질문 속의 B가 답변의 B가 반대라면[6] 명제 A는 거짓이다.
따라서 랜덤을 제외한 트루 혹은 폴스에게 질문할 경우 명제 A가 맞는지 틀리는지 확인 하기위해서는 질문 속의 대답과 실제 대답이 일치하느냐 안하느냐만 따지면 된다. 둘중 누구에게 물어보건 대답이 일치하면 명제 A는 참, 일치하지 않으면 거짓이다.

물론 이 방법은 '랜덤'에게는 통하지 않는다. 따라서 누가 '랜덤'이 아닌지를 알아내는 것을 먼저 해야한다.

3.2. 누가 랜덤이 아닌지 알아내기

  • 첫번째 질문: 중간에 있는 신에게 "만약 제가 당신 왼쪽에 있는 신이 '랜덤'이냐고 묻는다면, 당신의 대답은 'ja'인가요?"라고 질문하기

이 질문에서 ja라는 대답이 돌아왔다면 오른쪽에 있는 신은 랜덤이 아니란걸 확신할 수 있고, da라는 대답이 돌아왔다면 왼쪽에 있는 신은 랜덤이 아니란걸 확신할 수 있다.

ja라는 대답이 돌아왔다는 가정에서는 오로지 2가지 경우의 수만 존재한다.


1.이미 내가 질문을 한 중간에 있는 신이 랜덤이라서 방금 돌아온 대답은 아무런 의미가 없는 경우
2.가운데 있는 신이 트루 혹은 폴스이며, (질문에 넣은 것과 같은 단어가 대답으로 돌아왔다면 조건문의 질문이 참이라는 뜻이므로) 왼쪽에 있는 신은 랜덤인게 맞는 경우

물론 이 2개의 경우의 수 중에서 어떤게 맞는 건지 아직은 알 수 없지만, 일단 이 질문에서 대답이 ja로 돌아왔다는 것 자체만으로도 오른쪽에 있는 신이 랜덤일 경우의 수는 없다는 것 이다. 같은 논지에서, 만약 대답이 'da' 였다면 반대로 왼쪽에 있는 신이 랜덤이 아니란걸 알 수 있다.

이해를 돕기 위해 추가 설명하자면 이 질문에서 있을 수 있는 경우의 수는 내가 질문한 그 가운데 있는 신은 랜덤일 경우거나, 혹은 트루/폴스일 경우 단 2개의 경우의 수밖에 없다. 트루/폴스일 경우 1번 목차에서 나온 질문법을 통해서 상대가 트루인지 폴스인지 불확실해도 확실하게 진실을 알 수 있으니 랜덤이 오른쪽에 있는데 ja로 대답하거나, 랜덤이 왼쪽에 있는데 da로 대답할리가 없다. 그나마 질문에 거짓말을 할 가능성이 존재하는게 바로 가운데 있는 그 신이 '랜덤'이여서 50%의 확률로 거짓된 답변으로 돌아오는 경우의 수 뿐인데, 내가 질문을 한 가운데 있는 신이 랜덤이라는 시점에서 이미 왼쪽 오른쪽은 랜덤이 아니라는 말이 된다. 따라서 두 경우의 수 모두 어느쪽이 확실하게 랜덤이 아닌지를 알아낼 수 있다.
(해답이 아닌 문제 자체의 전제에 잘못된 점이 많음을 유의.)

이 첫번째 질문을 통해. 1차적으로 누가 랜덤이 아니라고 확신할 수 있는지 알 수 있다.

3.3. 랜덤이 아닌 신에게 질문하기

2번 목차의 방법을 통해 랜덤이 아니라고 확정된 왼쪽 혹은 오른쪽에 있던 신에게 이렇게 질문한다.
  • 두번째 질문: "만약 제가 당신에게 <당신은 '트루'입니까?> 라고 묻는다면 'ja'라고 대답할 것 입니까?"

일단 이 신은 랜덤이 아닌 것이 확정되었기에 무조건 트루거나 폴스 이거나 둘 중 하나일 수밖에 없다. 따라서 더 이상 랜덤의 불확실성을 걱정할 필요가 없으므로 ja 라는 답변이 돌아왔다면 그는 트루인거고, da라는 대답이 돌아왔다면 그는 폴스인 것 이다. 따라서 두번째 질문으로 내가 질문한 신의 정체를 알 수 있다.

똑같이 같은 신에게, 이번엔 가운데에 있는 신의 정체를 물어본다.
  • 세번째 질문: "만약 제가 당신에게 <가운데 있는 신은 '랜덤'입니까?> 라고 묻는다면 'ja'라고 대답할 것 입니까?"

이 질문에 대한 답이 ja 였을 경우 가운데에 있는 신이 랜덤인거고, da 였을 경우 내가 질문한 신의 정체와 랜덤을 제외한 남은 한명이 가운데 있는 신이다. 2명의 신의 정체를 알아낸 시점에선 남은 1명도 소거법으로 알아낼 수 있다. 고로 단 세번의 질문 만으로 모두의 정체를 밝혀내는데 성공한다. 여기까지는 위 TED 영상에서 설명되었던 풀이 방식이다.

3.4. 다른 풀이

위와 같은 분석을 보고 생각한다면, 두 번째 질문과 세 번째 질문이 바뀌어도 된다는 것을 알 수 있다.
랜덤이 누구인지와 질문하는 신의 정체 (트루 혹은 폴스) 를 알아내는 순서가 바뀌어도 되기 때문이다.
  • '랜덤이 아니라고 확정된 신에게 두번째 질문: "만약 제가 당신에게 <가운데 있는 신은 '랜덤'입니까?> 라고 묻는다면 'ja'라고 대답할 것 입니까?"

이 경우 현재 질문을 하고있는 신의 정체는 이미 트루/폴스 둘 중 하나라는게 확정된 상태이고, 중요한 점은 내가 질문을 하고있는 이 신 외에 또다른 트루/폴스 둘 중 하나인 신을 찾는 것 이다.

ja라는 답변이 돌아오면 가운데 있는 신이 랜덤이란걸 알 수 있으니 자동적으로 남은 한명이 또다른 트루/폴스일 것 이고, da 라는 답변이 돌아오면 가운데 있는 신은 또다른 트루/폴스인 것을 알 수 있다. 물론 이와 동시에 남은 한명도 랜덤이란걸 알 수 있다.

고로 여기까지 왔으면 이 상황에서는 랜덤이 누구인지, 그리고 남은 2명이 트루/폴스 인지 알고있는 상태이다. 따라서 마지막으로 할 일은 구체적으로 둘 중 누구 한명이 트루나 폴스냐를 밝혀내는 것 이다. 하나만 밝혀내도 자동적으로 남은 한명의 정체까지 알 수 있다.
  • 또다른 트루 혹은 폴스 둘 중 하나인 신에게 질문: "만약 제가 당신에게 <당신은 '트루'입니까?> 라고 묻는다면 'ja'라고 대답할 것 입니까?"

이 질문에서 ja가 돌아온다면 지금 질문한 신은 트루인거고, da가 돌아온다면 지금 질문한 신은 폴스인 것 이다. 고로 남은 한명의 정체도 자동적으로 밝혀지고 이미 랜덤인걸 알고있는 신까지 합쳐 3명 모두의 정체를 알아내게 된다.

4. 특이한 풀이: 머리 폭발

조금 변형된 문제의 경우, 모순을 이용해서 가능한 대답을 사실상 3가지로 만들어 푸는 방법도 있다. 2008년 Brian Rabern & Landon Rabern이 발표한 방법이다. # 물론 엄밀하게 따지면 원래 문제와 다르다고 할 수도 있지만, 위키피디아에서도 exploding god-heads라는 섹션을 두고 설명하는 등 꽤 널리 알려진 대답이기도 하다. 원본 문제의 허점[7]을 지적하고, 이를 기반으로 파생형 문제를 제기한 것이라 볼 수 있다.

예를 들어 "이 질문에 '아니요'라는 뜻의 단어로 대답하실 건가요?"라는 질문을 한다고 쳐 보자. 이 질문에는 ja로도 da로도 대답할 수 없지만, 신은 절대 실수를 하지 않으므로 이 질문을 듣는 신은 머리가 폭발(...)한다고 생각할 수도 있다. 이 모순을 이용하면 3번도 아니고 2번만에 모든 신의 정체를 파악할 수 있다.

일단 이 방법이 유효하려면 "정신상태"라는 것의 정의가 필요하다. 트루와 폴스는 항상 일관된 정신상태로 대답하겠지만, 랜덤은 질문할 때마다 정신상태가 바뀐다. 즉, 질문을 받을 때마다 랜덤은 트루가 되거나 폴스가 되는 것. 이렇게 정의한다면 위의 "만약 제가 [질문]이라고 묻는 다면, 당신의 대답은 ja인가요?"라는 질문을 랜덤에게 던져도 ja면 긍정, da면 부정이 된다.

본론으로 들어가면, 이 방법은 어떤 신 A를 지정해 다른 신 B를 골라 아래의 질문을 던지는 것.
  • 질문 A: "[(당신이 지금의 정신상태로 질문 A에 언제나 da로 대답하는 것) AND (B는 트루)] OR (B는 폴스)"라고 묻는다면 지금 정신상태로 당신의 대답은 ja인가요?
    • 대답이 ja일 경우: B가 폴스가 아니라면, 질문 A의 대괄호 속에 있는 말이 참이라야 한다. 이건 "당신이 지금의 정신상태로 질문 A에 언제나 da로 대답하는 것"이 참이라는 뜻이다. 하지만 대답이 ja였으므로 이건 모순이고, B는 폴스여야 한다.
    • 대답이 da일 경우: B가 랜덤이 아니라면, 따옴표 속에 있는 말이 거짓이므로 B는 폴스도 아니고, 따라서 B는 트루다. 그런데 대괄호 속에 있는 말이 또 거짓이므로, B는 트루가 아니거나 A가 이 질문에 ja로 대답해야 한다. 어느 쪽을 골라도 모순이므로, B는 랜덤이여야 한다.
    • A의 머리가 폭발할 경우: B가 폴스면 A는 당연히 ja라고 해야 한다. B가 랜덤이면 OR 양쪽에 있는 진술 모두 거짓이므로 A는 da라고 대답해야 한다. 이 사실들의 대우를 취하면, A의 머리가 폭발했다면 B는 트루일 수밖에 없다.

즉, 질문 한 방으로 신 하나의 정체가 단박에 확정된다. 이 방법으로 A에게 B에 대한 질문을 던지고, B에게 C에 대한 질문을 던지면 B, C의 정체를 알 수 있으니 두 번만에 모두 알아맞힐 수 있다. 그동안 머리 폭발한 신 있으면 책임은 없다

한편 약간 다른 설정으로, 랜덤은 진실/거짓 상관없이 완전 랜덤으로 대답하고, 트루와 폴스는 머리 폭발은 말고 대답을 못한다는 조건이 있으면 "정신상태"라는 설정을 제외하더라도 3번짜리 풀이를 만들 수 있다. 이때는 위의 3번짜리 풀이에서 첫 번째 질문을 트루나 폴스에게 던지면 대답을 못하는 질문으로 구성하면 된다. 랜덤은 그런 거 상관없이 ja나 da로 대답하므로 랜덤을 골라낼 수 있기 때문.

어쨌거나 변형된 문제라 논란이 있어서인지, 이 답을 제시한 Brian Rabern & Landon Rabern은 보충 논문을 내놓기도 했다.

[1] TED 판에서는 각각 TEE(항상 진실), EFF(항상 거짓), ARR(랜덤)으로 각색되었다. [2] TED 판에서는 이름을 알아내어 각 신에게 알맞은 유물을 전해주어야만 하는거로 각색되었다. [3] TED 판에서는 OZO와 ULU [4] 즉 질문에서 "당신의 대답은 ja 인가요?"라는 식으로 ja를 제시했을때, 신의 대답이 ja 라면 그것은 그 질문에 대한 긍정이고 반대로 신의 대답이 da 였다면 그 질문에 대한 대답은 부정이다. 반대로, da를 제시했을때 da가 대답이라면 긍정, ja가 대답이라면 부정이다. [5] 1.폴스는 2+2=9에 거짓('예')으로 대답한다. 2.두번째질문은 첫번째대답이 거짓인지 묻는다. 3. 실제로 첫번째 대답은 거짓이 아니었기에(폴스가 '예'라고 했으므로), 정직한 대답은 '아니오'이다. 4.폴스는 거짓을 얘기하므로 다시 거짓말해서 '예'라고 답한다. [6] 질문 안의 B는 '예'이고 답변자는 '아니오'라고 했을 경우, 반대로 질문 안의 B는 '아니오'이고 답변자는 '예'라고 했을 경우 [7] ja, da가 예, 아니오 중 어느 쪽에 대응되는가에 상관없이 대답 자체가 불가능한 질문을 던지는 경우. 만약 원본 문제가 '긍정 또는 부정을 가릴 수 없는 질문은 불가능하다' 와 같은 규칙을 지정했다면 이 허점은 보완된다.

분류