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.] wu : forums - NEW PROBLEM: The Gods of Gibberland
기존의 유사 문제들이
의 종류로 구분되었다면, 이 문제는 여기에서 한발짝 더 나아가, 아예 대답으로 나올 단어 후보조차도 모르는 상태에서 시작하는 문제이다. 그래서 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에 해당하는 단어보다 사전순으로 앞에 오는가”와 같은 문장을 포함해서 질문을 만들어 나가면 된다. 구체적인 질문은 진리표를 그려놓고서 적당히 조합하면 찾을 수 있다. 아래에 있는 정답은 포럼 스레드에 달렸던 해답이다.
Ask God A: Q1: Is the word that means “yes” alphabetically before the word that means “no” if and only if you are GibberKnight?
([yes] is BEFORE [no]) == (A is Knight)?
God A answers: “foon”.
경우의 수:
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]
Ask God A: Q2: Does “foon” mean “yes” if and only if you are GibberKnave?
(foon means [yes]) == (A is Knave)?
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.
위의 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이다. (원문과 살짝 다른데 원문에서 실수한 것 같다)
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'.
경우의 수
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]
Ask God A: “Does the word for 'no' come alphabetically before the word for 'yes'?”
경우의 수
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의 정체를 파악할 수 있다.
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.
B의 가능한 후보가 2가지라면, 한개의 질문으로 둘 중 어느 쪽인지를 밝히는 것은 어렵지 않다. 원문에서는 “what would you say if I asked you…” 트릭을 써서 풀수 있다고 언급했고, 실제로도 가능하다. 하지만 앞에 들었던 대답을 이용해서 'A1이 [yes]라는 뜻이니?' 라는 질문을 섞어서 할 수도 있다