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/
Received on Tue Oct 12 2004 - 05:33:19 PDT