You made a relevant decomposition of the problem,
and you are on the right track. Actually I'm not sure the "ja" "da"
McCarthy's amelioration adds anything deep to the problem.
It will be enough to take into account that a double negation
gives an affirmation.

Bruno



At 16:55 11/10/04 -0400, Jesse Mazer wrote:
Bruno Marchal wrote:

As a Price, I give you the (known?) Smullyan McCarthy
puzzle. You are in front of three Gods: the God of Knights, the
God of Knaves, and the God of Knives. The God of Knight always
tells the truth. The God of Knaves always lies, and the God of Knives
always answers by "yes" or "no" randomly.
You must find which is which, through some questions.
You can ask no more than three yes-no (answerable) questions.
(Each question must be asked to one God, but you can ask
more than one question to a God; only then there will be a
God you can no more ask a question).

Playing around with this for a while, I realized you can always trick the knave into giving the same answer as the knight to any question "X" by asking the more complicated question, "If I were to ask you question X, would you answer 'yes'?" The knight will always give the same answer to this question as he would to the question X itself, while the knave will always give the opposite answer that he would if you had actually asked him X, which means he will always answer the same as the knight!


With this trick, the problem reduces to a simpler one where you have three guys with different names--say, Huey, Dewey, and Louie--and you know Huey and Dewey always tell the truth while Louie always answers randomly, and you have to figure out each guy's name with only three questions. In this case, you could ask the first guy, "is the second guy Louie?" Then if he answers "yes", you know the third guy must be either Huey or Dewey, so you ask the third guy "are you Huey?" and then ask "is the first guy Louie?" and you're set. On the other hand, if the first guy answered "no" to your first question, then you know the second guy is either Huey or Dewey, so you can ask the second guy the same two questions.

Translating this back into the 3 Gods, problem, your first question should be to ask the first God "If I asked you 'is the second God the God of Knives', would you say 'yes'?" If the first God answers "yes", you know the God of Knives is either the first or the second God, so you can ask the third God, "If I asked you 'are you the God of Knights', would you say 'yes'?" and after that you can ask the third God "If I asked you 'is the first God the God of Knives', would you say 'yes'?" and this will be enough to tell you the identity of all three Gods. On the other hand, if the answer to your first question was "no", then you know the God of Knives is either the first or the third God, so you would ask the *second* God the same two subsequent questions as above.

And (added McCarthy) I let you know that all the Gods, although
they understand English, will  answer the yes-know question by
either "JA" or "DA", and you are not supposed to know which
means "yes" and which means "no".

Ugh, I'll have to think about that some more...but again, this is equivalent to a problem where you have three guys named Huey, Dewey and Louie, and Huey and Dewey always tell the truth while Louie answers randomly, but they all answer with "JA" or "DA" and you don't know which word means yes and which means no. If anyone else can figure it out feel free to jump in.


Jesse


http://iridia.ulb.ac.be/~marchal/



Reply via email to