7월의 퍼즐에 참여해주신 모든 분들께 감사드립니다!

7월의 퍼즐에 참여해주신 분 중 정답과 함께 좋은 풀이를 보내주신 김규현 님께
HORIZON에서 문화상품권을 전달드릴 예정입니다.

7월의 퍼즐 문제 보러가기


본 문제는 스멀리언의 저서 ‘Satan, Cantor & Infinity’의 1.7절 ’The Island of Partial Silence’에 2.9절 ‘The Planet Og’를 덧붙여 조금 더 어렵게 확장한 것이다.

본 문제는 기사-건달의 경우보다 복잡한 것 같지만 종족과 거주지를 모두 무시하는 질문이므로 실질적으로는 참과 거짓만 말하는 사람들이 모인 기사-건달 퍼즐과 경우가 같다. 즉, 종족이나 거주지를 굳이 언급하지 않아도 원하는 질문을 만들 수 있다.

소기의 목적을 달성할 수 있는 질문은 다음과 같다.

“‘당신이 진실로 이 질문에 「아니요」라고 답할 것’과 ‘당신이 거짓으로 이 질문에 「예」라고 답할 것’ 중 최소 하나가 참입니까?”


답변자가 참말을 한다고 가정하자. 전체 질문에 참으로 답해야 하는데 후자인 ‘당신이 거짓으로 이 질문에 「예」라고 답할 것’이 항상 거짓이 되므로 전자인 ‘당신이 진실로 이 질문에 「아니요」라고 답할 것’이 참이어야 한다. 이미 참말을 한다고 가정했으므로 ‘이 질문에 「아니요」라고 답할 것’의 참-거짓만 판단하면 된다. 그런데 ‘예’든 ‘아니요’든 모든 답이 질문에 거짓이 되기 때문에 답변자는 어떤 답도 할 수 없다.

이번에는 답변자가 거짓말을 한다고 가정하자. 전체 질문에 거짓으로 답해야 하는데 전자인 ‘당신이 진실로 이 질문에 「아니요」라고 답할 것’은 항상 거짓이 되므로 후자인 ‘당신이 거짓으로 이 질문에 「예」라고 답할 것’만 거짓이 되면 된다. 이미 거짓말을 한다고 가정했으므로 ‘이 질문에 「예」라고 답할 것’에 대한 참-거짓만 판단하면 된다. 그런데 ‘예’든 ‘아니요’든 모든 답이 질문에 진실이 되기 때문에 답변자는 어떤 답도 할 수 없다.

 

 

보너스 문제 해설

보너스 문제는 종족과 거주지를 고려해야 하므로 전과 달리 더 복잡해지는 것이 맞다.각 경우 다음과 같은 질문들이 답이 될 수 있다.

1) ‘당신이 펭귄족이고 이 질문에 예라고 답할 것’과 ‘당신이 곰족이고 이 질문에 아니라고 답할 것’ 중 최소 하나가 참입니까?

2) ‘당신이 남극대륙에 살고 이 질문에 예라고 답할 것’과 ‘당신이 북극 대륙에 살고 이 질문에 아니라고 답할 것’ 중 최소 하나가 참입니까?

두 문장은 모두 아래와 같은 틀에 기초하고 있다.

‘당신이 X이고 이 질문에 예라고 답할 것’과 ‘당신이 X가 아니고 이 질문에 아니라고 답할 것’ 중 최소 하나가 참입니까? …(*)

이제 이 외계인이 ‘나는 X이다’라고 말할 수 있는지 생각해보자.

a) 외계인이 (*)에 예라고 한 경우
a-1) 먼저 외계인이 진실을 말하는 타입이라 하자. 그러면 (*) 속 두 질문 중 최소 하나가 참이어야 한다. 그런데 외계인은 이미 예라고 답했으므로 ‘당신이 X가 아니고 이 질문에 아니라고 답할 것’은 참이 될 수 없다. 따라서 ‘당신이 X이고 이 질문에 예라고 답할 것’이 참이 되어야 한다. ‘그리고’의 원리에 의해 그 외계인은 X이다. 외계인은 진실을 말하므로 ‘나는 X이다’라고 말할 수 있다.

a-2) 다음 외계인이 거짓을 말하는 타입이라 하자. 그러면 (*) 속 두 질문 모두 거짓이 되어야 한다. 특히, 예라고 답했음에도 불구하고 ‘당신이 X이고 이 질문에 예라고 답할 것’이 거짓이 되어야하기 때문에 ‘그리고’의 원리에 의해 그 외계인은 X가 아니다. 외계인은 거짓을 말하므로 ‘나는 X이다’라고 말할 수 있다.

b) 외계인이 (*)에 아니라고 한 경우
b-1) 먼저 외계인이 진실을 말하는 타입이라 하자. 그러면 (*) 속 두 질문 모두 거짓이 되어야한다. 특히, 아니라고 답했음에도 불구하고 ‘당신이 X가 아니고 이 질문에 아니라고 답할 것’이 거짓이 되어야 하므로 ‘그리고’의 원리에 의해 그 외계인은 X이다. 외계인은 진실을 말하므로 ‘나는 X이다’라고 말할 수 있다.

b-2) 다음 외계인이 거짓을 말하는 타입이라 하자. 그러면 (*) 속 두 질문 중 최소 하나가 참이어야 한다. 그런데 외계인은 이미 아니라고 답했으므로 ‘당신이 X이고 이 질문에 예라고 답할 것’은 참이 될 수 없다. 따라서 ‘당신이 X가 아니고 이 질문에 아니라고 답할 것’이 참이 되어야 한다. ‘그리고’의 원리에 의해 그 외계인은 X가 아니다. 외계인은 거짓을 말하므로 ‘나는 X이다’라고 말할 수 있다. 종합하면, 외계인이 (*)에 예든 아니든 답을 한 경우에 ‘나는 X이다’라고 말할 수 있다.

또한 ‘나는 X이다’라고 말한 외계인이 있었을 때 그가 어떤 경우든 (*)에 답할 수 있음도 비슷한 논증을 거쳐 쉽게 보일 수 있다.

이상의 설명으로 우리는 어떤 외계인이 (*)에 (예든 아니든) 답을 했을 경우, 그리고 오직 그 경우에 한해 ‘나는 X이다’라고 말할 수 있다는 것을 알았다. 거꾸로 얘기해, 어떤 외계인이 ‘나는 X이다’라고 말할 수 없다는 것과 그가 (*)에 어떤 답도 할 수 없다는 것이 동치이다. 따라서 X를 잘 선택하면 어떤 조건의 문제든 해결할 수 있다.

1) ‘나는 펭귄족이다.’는 오직 남극대륙에 거주하는 외계인만이 말할 수 있다. 따라서 “‘당신이 펭귄족이고 이 질문에 예라고 답할 것’과 ‘당신이 곰족이고 이 질문에 아니라고 답할 것’ 중 최소 하나가 참입니까?”라는 질문에는 오직 남극대륙 거주 외계인만이 답할 수 있다.

2) ‘나는 남극대륙 거주자이다.’는 오직 펭귄족 외계인만이 말할 수 있다. 따라서 “‘당신이 남극대륙에 살고 이 질문에 예라고 답할 것’과 ‘당신이 북극 대륙에 살고 이 질문에 아니라고 답할 것’ 중 최소 하나가 참입니까?”라는 질문에는 오직 펭귄족 외계인만이 답할 수 있다.

이 원리를 쓰면 본 문제의 답도 여러 개 구할 수 있게 된다. 이를테면 ‘나는 출신지에 살고 있지 않다’는 그 어떤 외계인도 말할 수 없다. 따라서 “‘당신이 출신지에 살지 않고 이 질문에 예라고 답할 것’과 ‘당신이 출신지에 살고 이 질문에 아니라고 답할 것’ 중 최소 하나가 참입니까?”라는 질문에는 어떤 외계인도 답할 수 없다.

 

 

이 이외에도 KPP의 이충명 님의 답도 소개한다.

본 문제의 답

당신이 이 질문에 거짓으로 답할 것과 당신이 이 질문에 예라고 대답할 것이 동치입니까?

보너스 문제의 답

1) 당신이 남극대륙 거주지인 것과 당신이 이 질문에 진실로 답할 것과 동치라는 것이 당신이 이 질문에 예라고 대답하는 것과 동치입니까?

2) 당진이 펭귄족인 것과 당신이 이 질문에 진실로 답할 것과 동치라는 것이 이 질문에 예라고 대답하는 것과 동치입니까?

 

 


다음은 7월의 정답자로 선정된 김규현 님의 해설입니다.

 

지문에 나와 있는 “당신은 이 질문에 ’예‘라고 답할 것인가요?” 라는 자기 지시적 질문을 활용하여 문제를 풀도록 한다.

질문 A: “당신은 이 질문에 ’예‘라고 답할 것인가요?” 라는 질문은 어떤 답을 하던 참이 되고,
질문 B: “당신은 이 질문에 ’아니오‘라고 답할 것인가요?” 라는 질문은 어떤 답을 하던 거짓이 된다.

따라서, 항상 참을 말하는 외계인에게는 질문 B가 되고 항상 거짓을 말하는 외계인에게는 질문 A가 되는 복합 질문을 구성하면 된다.

따라서 아래의 질문은 문제의 조건을 만족한다.

질문: 당신이 출신지에 거주하고 있으면 당신은 이 질문에 ‘아니오’라고 답하고, 그렇지 않고 출신지에 거주하지 않고 있으면 ‘예’라고 답할 것인가요?

증명:

당신이 출신지에 거주하고 있으면 (P) 당신은 이 질문에 ‘아니오’라고 답하고 (Q), (AND) 그렇지 않고 출신지에 거주하지 않고 있으면 (R) ‘예’라고 답할 것인가요 (S)?
즉, P→Q ∧ R→S 일 때,

1) 출신지에 거주하는 외계인인 경우 (즉, 남극에 거주하는 펭귄족 또는 북극에 거주하는 곰족):
R이 거짓이므로 R→S 는 참, P가 참이므로 Q가 참이면 대답은 참, Q가 거짓이면 대답은 거짓이 된다. 즉 질문은 “당신은 이 질문에 ‘아니오’라고 답할 것인가요?”와 동치가 되는데 이 질문은 어떤 대답을 하건 거짓이 되므로, 어떤 답도 할 수 없다.

2) 출신지에 거주하지 않는 외계인인 경우 (즉, 북극에 거주하는 펭귄족 또는 남극에 거주하는 곰족):
P가 거짓이므로 P→Q 는 참, R이 참이므로 S가 참이면 대답은 참, S가 거짓이면 대답은 거짓이 된다. 즉 질문은 “당신은 이 질문에 ‘예’라고 답할 것인가요?”와 동치가 되는데 이 질문은 어떤 대답을 하건 참이 되므로, 어떤 답도 할 수 없다.

보너스 문제 1)
남극대륙 거주자 중 펭귄족에게는 질문 A가 되고 곰족에게는 질문 B가 되고, 북극대륙 거주자 중 펭귄족에게는 질문 A가 되고 곰족에게는 질문 B가 되는 복합 질문을 구성하면 된다. 즉, 펭귄족에게는 질문 A, 곰족에게는 질문 B가 되는 복합 질문이면 되므로,

질문: “당신이 펭귄족이라면 당신은 이 질문에 ‘예’라고 답하고, 곰족이라면 ‘아니오’라고 답할 것인가요?” 라 하면 조건을 만족한다.

보너스 문제 2)
펭귄족 중 남극대륙 거주자에게는 질문 A가 되고 북극 대륙 거주자에게는 질문 B가 되고, 곰족 중 남극대륙 거주자에게는 질문 A가 되고 북극 대륙 거주자에게는 질문 B가 되는 복합 질문을 구성하면 된다. 즉, 남극대륙 거주자에게는 질문 A, 북극대륙 거주자에게는 질문 B가 되는 복합 질문이면 되므로,

질문: “당신이 남극대륙 거주자라면 당신은 이 질문에 ‘예’라고 답하고, 북극대륙 거주자라면 ‘아니오’라고 답할 것인가요?” 라 하면 조건을 만족한다.

안진후
고등과학원 계산과학부 연구원, KPP(Korean Puzzle Party)