가장 어려운 논리 퍼즐

 


TED의 설명영상, 한국어 자막을 지원한다.
1. 개요
2. 문제
3. 해답
3.1. 질문의 방식
3.2. 누가 랜덤이 아닌지 알아내기
3.3. 랜덤이 아닌 신에게 질문하기
3.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 인가요?"'''라고 질문했다고 치자.
  • 만약 ja가 '맞다'이고 da가 '아니다'라는 뜻일 경우
    • 질문한 상대가 '트루'일 경우: '2+2=4?'라고 질문할 경우 ja(참)이라 대답할테고, 그 질문에 대한 답이 ja 냐고 대답할 것이냐는 질문도 마찬가지로 문제없이 ja라고 대답할 것 이다.
    • 질문한 상대가 '폴스'일 경우: 폴스에게 '2+2=4?' 라고만 질문했다면 거짓말로 da(아니다) 라고 대답할 것 이다. 고로 '그 질문에 ja(맞다)라고 대답할 것 이냐?' 라는건 폴스 입장에선 사실이 아니지만, 이 질문에 대한 답도 거짓말을 해야하니 사실이라고 해야한다. 따라서 '그 질문에 ja라고 대답할 것 이냐'라는 질문에서는 긍정인 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 라고 답한다.
즉, ja와 da중 어느게 예/아니오 인지 모르는 상태이며 질문한 상대가 트루인지 폴스인지도 모르는 상태지만 질문에서 ja를 제시하든 da를 제시하든, 어찌되었건 내가 질문에서 제시한 단어가 동일하게 대답에서 제시된다면 조건문으로 넣은 질문이 사실이라는 것, 질문에서 제시한 단어와 반대의 단어가 대답으로 돌아왔다면 조건문에 넣은 질문은 사실이 아니라는게 '''모든 경우의 수에서 동일하게 적용된다.''' 이는 긍정+긍정과, 부정+부정 모두 긍정이라는 논리학에 기반한다.
물론 이 방법은 '랜덤'에게는 통하지 않는다. 따라서 누가 '랜덤'이 아닌지를 알아내는 것을 먼저 해야한다.

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명 모두의 정체를 알아내게 된다.

[1] TED 판에서는 각각 TEE(항상 진실), EFF(항상 거짓), ARR(랜덤)으로 각색되었다.[2] TED 판에서는 이름을 알아내어 각 신에게 알맞은 유물을 전해주어야만 하는거로 각색되었다.[3] TED 판에서는 OZO와 ULU[4] 즉 질문에서 "당신의 대답은 ja 인가요?"라는 식으로 ja를 제시했을때, 신의 대답이 ja 라면 그것은 그 질문에 대한 긍정이고 반대로 신의 대답이 da 였다면 그 질문에 대한 대답은 부정이다. 반대로, da를 제시했을때 da가 대답이라면 긍정, ja가 대답이라면 부정이다.

분류