Re: S, B, and a puzzle by Boolos, Smullyan, McCarthy

From: Jesse Mazer <lasermazer.domain.name.hidden>
Date: Mon, 11 Oct 2004 16:55:19 -0400

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
Received on Mon Oct 11 2004 - 16:57:04 PDT