====== The Gods of Gibberland ======

===== 문제 =====

==== 출처 ====
  * 최초로 이 문제가 올라온 곳은 [[https://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1028840975|wu : forums]] 라는 개인이 운영하는 (하지만 꽤 많은 유저가 활동하는) 포럼인것 같다. 2002년에 Eric Yeh 라는 사람이 자신이 만든 퍼즐을 풀어보라고 이 문제를 올렸다

==== 원문 ====
<blockquote>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.]
<cite>[[https://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1028840975|wu : forums - NEW PROBLEM:  The Gods of Gibberland]]</cite>
</blockquote>

===== 풀이 =====
기존의 유사 문제들이 
  * 대답이 'yes', 'no'로 해주는 문제
  * 그리고 여기서 발전한, 대답을 'da', 'ya'로 해주는 문제. (어느쪽이 'yes'에 해당하고 어느쪽이 'no'에 해당하는지 모름)
의 종류로 구분되었다면, 이 문제는 여기에서 한발짝 더 나아가, 아예 대답으로 나올 단어 후보조차도 모르는 상태에서 시작하는 문제이다.
그래서 da/ya문제의 메인 아이디어인, 'da'가 'yes'라는 뜻이니? 와 같은 질문을 맨 처음에 하는 것이 불가능하다.

이 문제의 조건을 보면
  * 첫번째 질문을 무엇으로 하든 첫번째 대답으로는 처음 듣는 단어가 나온다. 
  * 두번째 질문에 대해서는 무슨 질문을 하든, 대답으로 나올수 있는 것은 처음 대답과 같은 단어, 또는 처음 대답과 다른 단어이다.
즉, 처음 두개의 질문으로는, 두 대답이 같은 경우와 두 대답이 다른 경우, 이렇게 두가지로만 분류할 수 있다, 여기에 세번째 질문을 추가하게 되면 총 4개의 경우로 분류가 가능하다. 그러나 A,B,C에 세가지 신이 위치하는 방법은 3!=6가지로 분류 가능한 경우의 수보다 크므로, 어떤 질문을 하더라도 구분하지 못하는 경우가 생긴다. 이것을 해결하기 위해서는 참신한 아이디어가 필요하다.

그 참신한 아이디어는 첫번째 대답(=A1)과 두번째 대답(=A2)를 A1==A2, A1!=A2의 두가지로 분류하는 것이 아니라, A1<A2, A1==A2, A1>A2의 세가지로 분류하는 것이다. 이렇게 한다면 세번째 질문까지 추가했을때 총 6가지의 경우로 분류할 수 있다! 이제 남은 일은 구체적인 방법을 찾는 것 뿐. 임의의 두 단어에 대해서 비교를 가능하게 하기 위해서는, 모든 단어에 total order를 부여해 주면 된다. 가장 간단한 방법은 두 단어의 lexicographical order를 비교하는 것이다. 이것을 활용하려면 질문에서도 "yes에 해당하는 단어가 no에 해당하는 단어보다 사전순으로 앞에 오는가"와 같은 문장을 포함해서 질문을 만들어 나가면 된다. 구체적인 질문은 진리표를 그려놓고서 적당히 조합하면 찾을 수 있다. 아래에 있는 정답은 포럼 스레드에 달렸던 해답이다.

===== 정답 =====
  * "yes에 해당하는 단어가  no에 해당하는 단어보다 사전순으로 앞에 오는가"를 질문에 포함시켜서, 처음 2번의 질문으로 경우의 수를 세가지로 나눈다는 핵심 아이디어를 파악하면, 정답이 될 수 있는 질문 조합은 다양하게 만들 수 있다.
  * 원래 스레드에서의 정답자는 처음에는 iff 컨디션을 이용해서 성립은 하지만 다소 지저분한 해답을 만들었고, 그 뒤 조금 다듬어서 훨씬 더 간단한 형태의 해답을 제시했다.
  * 원래 스레드에 올라왔던 해답에 박스 표시된 해설을 추가해서 붙였다.

==== 처음 제시된 해답 ====
Ask God A:
Q1: Is the word that means "yes" alphabetically before the word that means "no" if and only if you are GibberKnight?
<blockquote>([yes] is BEFORE [no]) == (A is Knight)?</blockquote>
 
God A answers: "foon".
<blockquote>
경우의 수:

| Case# | A?     | [yes] is BEFORE [no]? | A is Knight | ([yes] is BEFORE [no]) == (A is Knight) | 대답 (What does foon mean?)|
| 1     | Knight | True | True | True | [yes] |
| 2     | Knight | False | True | False | [no] |
| 3     | Knave | True | False | False | [yes] |
| 4     | Knave | False | False | True | [no] |
| 5     | Knave | True | False | False | [yes] |
| 6     | Knave | False | False | True | [yes] |
</blockquote>
 
Ask God A:
Q2: Does "foon" mean "yes" if and only if you are GibberKnave?
<code>(foon means [yes]) == (A is Knave)?</code>
 
Case 1: God A answers "foon". In this case, he is GibberKnave
Case 2: God A answers "blatz". In this case, he is GibberKnexus
Case 3: God A answers "worple". In this case, he is GibberKnight.
 
<blockquote>
위의 1번부터 6번까지 6가지 경우에 대해서

| | foon means [yes] | A is Knave | (foon means [yes]) == (A is Knave) | 대답 | 대답에 해당하는 단어 |
|1| True  | False | False | [no]  | foon 보다 사전순으로 뒤. (ex: worple)|
|2| False | False | True  | [yes] | foon 보다 사전순으로 뒤. (ex: worple)|
|3| True  | True  | True  | [no]  | foon 보다 사전순으로 앞. (ex: blatz)|
|4| False | True  | False | [yes] | foon 보다 사전순으로 앞. (ex: blatz)|
|5| True  | False | False | [yes] | foon |
|6| True  | False | False | [yes] | foon |

두번째 대답이 첫번째 대답보다 뒤에 있는 단어면 Knight, 앞에 있는 단어면 Knave, 같은 단어면 Knexus이다. (원문과 살짝 다른데 원문에서 실수한 것 같다)
</blockquote>

==== 간단하게 다듬은 해답 ====
Ask God A: "Does the word for 'yes' come alphabetically before the word for 'no'?"
 
GibberKnight will say whichever answer word comes alphabetically first. GibberKnave will say whichever answer word comes alphabetically second. GibberKnexus will say whichever answer word means 'yes'.

<blockquote> 
경우의 수 
| Case#  |  A?    | Q1. [yes] is BEFORE [no]? | A1  |
| 1 | Knight | True                  | [yes]|
| 2 | Knight | False                 | [no] |
| 3 | Knave  | True                  | [no] |
| 4 | Knave  | False                 | [yes]|
| 5 | Knexus | True                  | [yes]|
| 6 | Knexus | False                 | [yes]|
</blockquote>

Ask God A: "Does the word for 'no' come alphabetically before the word for 'yes'?"

<blockquote>
경우의 수 
| Case# |  A?    | Q2. [no] is BEFORE [yes]?  | A2  | (A1) | A1과 A2의 관계 |
| 1 | Knight | False                  | [no] | [yes] | A1([yes]) 가 A2([no])보다 앞 |
| 2 | Knight | True                   | [yes]| [no]  | A1([no]) 가 A2([yes])보다 앞 |
| 3 | Knave  | False                  | [yes]| [no]  | A1([no]) 가 A2([yes])보다 뒤 |
| 4 | Knave  | True                   | [no] | [yes] | A1([yes]) 가 A2([no])보다 뒤 |
| 5 | Knexus | False                  | [yes]| [yes] | A1([yes]) 와 A2([yes])가 같다 |
| 6 | Knexus | True                   | [yes]| [yes] | A1([yes]) 와 A2([yes])가 같다 |

이제 첫번째 대답(A1)과 두번째 대답(A2)의 관계로 A의 정체를 파악할 수 있다.
</blockquote>

If the answers to the two questions are the same, God A is GibberKnexus, and his answer means 'yes'. Ask God B: "Is 2+2 equal to 4?" If his answer is the same as God A's answers, he's the Knight, otherwise he's the Knave.
 
If the answers to the two questions differ and the answer to question 1 precedes the answer to question 2 alphabetically, he's a Knight. If the answer to question 2 precedes the answer to question 1, he's a knave. Either way, you can use the iff trick combined with the "what would you say if I asked you..." trick to determine which of the other Gods is which.

<blockquote>
B의 가능한 후보가 2가지라면, 한개의 질문으로 둘 중 어느 쪽인지를 밝히는 것은 어렵지 않다. 원문에서는 "what would you say if I asked you..." 트릭을 써서 풀수 있다고 언급했고, 실제로도 가능하다. 하지만 앞에 들었던 대답을 이용해서 'A1이 [yes]라는 뜻이니?' 라는 질문을 섞어서 할 수도 있다
  * A가 Knexus라면, 우리는 이미 [yes]에 해당하는 단어을 알고 있으니, B에게 true인 명제 (예를 들면, 1+1=2 입니까?)를 물어봐서 대답이 [yes]이면 Knight, 처음 듣는 단어([no)이면 Knave로 구분할 수 있다
  * A가 Knight 라면, B에게 "A1이 [yes]라는 뜻이거나, 너가 Knight니?" 라고 물어본다
    * B가 Knave라면, A1이 [yes]면 [no]로 대답하고, A1이 [no]면 [yes]로 대답한다, 즉 언제나 A1과 다른 단어로 대답을 한다
    * B가 Knexus라면, A1이 [yes]라면 [yes]로 대답하고, A1이 [no]면 [no]로 대답한다. 즉 언제나 A1과 같은 단어로 대답을 한다
    * 즉, A1과 같은 단어로 대답하면 B는 Knave, 다른 단어로 대답하면 B는 Knexus.
  * A가 Knave 라면, B에게 "A1이 [yes]라는 뜻이고, 너가 Knight니?" 라고 물어본다
    * B가 Knight라면, A1이 [yes]면 [yes]로 대답하고, A1이 [no]면 [no]로 대답한다, 즉 언제나 A1과 같은 단어로 대답을 한다
    * B가 Knexus라면, A1이 [yes]라면 [no]로 대답하고, A1이 [no]면 [yes]로 대답한다. 즉 언제나 A1과 다른 단어로 대답을 한다
    * 즉, A1과 같은 단어로 대답하면 B는 Knight, 다른 단어로 대답하면 B는 Knexus.
</blockquote>