천국과 지옥 6 (T,F,XOR)

인터넷 퍼즐포럼에서 접한 주옥 같은 문제. 필자는 처음에 머리로만 4시간 가량 풀다 포기. 힌트를 보고도 8시간 진리표 작성해서 간신히 완성. 근데 답을 보니 감탄이 절로 나옴. 2002년 하버드 대학(아마도)의 Eric Yeh가 인터넷에 올린 작품입니다. (약간 각색하며 보다 명료하고 어려워지게 비틈. 원문은 아래에 붙임. 주의!!! 아래 덧글에 링크가 있습니다. 포럼 링크-문제, 힌트, 답까지 볼 수 있음)

 

<천국과 지옥 6 (T,F,XOR)>

 

나그네가 저승에 갔습니다. 갈림길에 세 명이 서 있는데 각각 A, B, C라고 적힌 옷을 입고 있습니다. 베드로가 옆에서 말합니다.

 

"이 세 명은 각각 참족, 거짓족, 삐딱이족의 신이라네. 참족은 참말만 하고 거짓족은 거짓말만 하는데 삐딱이족은 XOR 연산을 하지. 즉, 삐딱이족은 같은 질문을 참족이 받았을 때의 진리치(a)와 거짓족이 받았을 때의 진리치(b) 두 개로써 a XOR b 연산을 한다는 뜻일세. 각 신들은 자신이 속한 종족과 같이 행동한다네. (예 : 참족의 신은 항상 참말만 함)

 

신들은 예/아니오로 대답할 수 있는 질문에는 뭐든 답할 수 있는 능력을 갖고 있지. 자네는 이제부터 예/아니오로 대답할 수 있는 질문을 셋(3) 할 수 있네. 한 질문은 한 명의 신에게만 해야 해. 두 명 이상 신에게 한 질문을 하면 안돼. 한 명의 신에게 질문 둘 이상을 할 수도 있는데 그 경우엔 질문을 받지 않는 신이 생기겠지. 어떤 질문을 듣고 답을 들은 후 그걸 참조하여 다음 질문을 설계할 수 있네. (어떤 경우이든 세 질문이 같아야 하는 것은 아님)

 

신들은 자네의 질문에 '예' 또는 '아니오'를 뜻하는 이 세계 말로 대답할 텐데, 그 중 하나는 모음, 다른 하나는 자음으로 시작한다는 점 이외엔 알려주지 않겠네.  어떤 단어인지 직접 겪어보게나. 자, 세 질문으로써 A, B, C가 각각 어느 종족의 신인지 맞추면 천국으로 갈 수 있네."

 

전제 : 1. 자기지시적인 문장은 허용되지 않습니다. (예 : 이 문장은 참일까요?)

         2. 삐딱이족이라면 어떻게 답할까요? 따위 문장도 허용되지 않습니다. (순환 loop에 빠질 우려)

 

문제 : 어떤 질문을 어떤 순서와 방식으로 해야 할까요?

 

참고 : 삐딱이족의 연산 방식

'a XOR b' 는, (a,b)=(T,F) 또는 (F,T)일 때 참, (a,b)=(T,T) 또는 (F,F)이면 거짓임.

삐딱이족은 같은 질문을 참족이 받고 답하는 진리값(a)과 거짓족이 받고 답하는 진리값(b)을 XOR함.

 

예를 들어, (A, B, C)= (삐딱이족, 참족, 거짓족) 순서로 섰을 때 A에게 질문하는 경우,

----------------------------------------------------------------------------

      질문                           (a) 참족       (b)거짓족           A(삐딱이족)의 답

----------------------------------------------------------------------------

1+1=2 입니까?                        예                아니오          (TF이므로)    예

당신은 참족입니까?                예                   예              (TT이므로) 아니오

A는 삐딱이족입니까?              예                아니오           (TF이므로)   예

A는 참족입니까?                 아니오                예              (FT이므로)   예

당신은 거짓족입니까?          아니오             아니오           (FF이므로) 아니오           

----------------------------------------------------------------------------

 

(아래는 원문입니다)

THE GODS OF GIBBERLAND

There are three omniscient gods sitting in a chamber:  GibberKnight, GibberKnave, and GibberKnexus, the gods of the knights, knaves, and knexuses of Gibberland.  Knights always answer the truth, knaves always lie, and knexuses always answer the xor of what the knight and knave would answer.
 
Unfortunately, the language spoken in Gibberland is so unintelligible that not only do you not know which words correspond to "yes" and "no", but you don't even know what the two words that represent them are!  All you know is that there is only one word for each.
 
With three questions, determine which god is which.
 
[Notes:
 
Standard:  (Rules that are generally assumed unless otherwise noted.) The gods only answer yes/no questions.  Each god answers in the single word of their language as appropriate to the question; i.e. each god always gives one of only two possible responses, one affirmative and one negative (e.g. they would always answer "Yes" rather than "That would be true").  Each question asked must be addressed to a single specific god; asking one question to all the gods would constitute three questions.  Asking a single god multiple questions is permissible.  The question you choose to ask and the god you choose to address may be dynamically chosen based on the answers to previous questions.
 
Specific:  Because of possible loop conflicts, you may not ask any questions regarding how a knexus would answer.]
-----
Yes, this problem is designed to be anti-programming, anti-da/ya-algorithm, and besides that, beyond the traditional da-ya problem.  I have written up some hints on it, but I don't want to hand them out quite yet...  Who knows, maybe you'll all find it to be trivial!