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

From: Eric Cavalcanti <eric.domain.name.hidden>
Date: Wed, 13 Oct 2004 12:15:20 +1000

On Mon, 2004-10-11 at 22:51, Bruno Marchal wrote:

> As a Price, I give you the (known?) Smullyan McCarthy

As a Price, or a Prize? :)

> 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).
> 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".

Wow, that was a hard one!
I have been thinking about it all day, but I think
I got to the solution. Let's see...

I developed a whole method for solving this kind of
problem. :)

Labelling the Knights' God as T, the Knaves' God as F,
and the Knives' God as R, we have 6 possible 'states'
we want to distinguish, which are all the permutations
of them. I'll make 3 questions, which can have two
possible outcomes each, "JA"(J) or "DA"(D). This means
that in the end my "experiment" has 8 possible outcomes.

>From this initial analysis it is clear that I cannot aim
to ask questions which would give me information about
the statements "JA=YES" or "JA=NO", because for that I
would need to distinguish between 12 states.
But since I have 2 outcomes more than states, it is
possible that I might in some cases get this last answer,
but only as a bonus.

So I make a table where I try to fit a set of 3
questions whose outcomes are going to distinguish these
states. One possible table is the following:

State 1st J D JJ JD DJ DD Final
-----------------------------------------------
TRF J J J JJJ
TFR D J J DJJ
FRT J D J JDJ
FTR D D J DDJ
RTF J/D J D D D JJD/DDD
RFT J/D D J D D JDD/DJD
-----------------------------------------------

The blank spaces mean that we don't care what would
be the answer in those cases, because they have been
already ruled out. It's important to leave blank
spaces in at least two lines which correspond to
'R's in the same column, because we can always make
the question to the the God in that column so that
we can arrange the random answers to fall in those
places. The columns 'J', 'JJ' and so on indicate the
outcomes that I wish the next question to have given
outcome 'J', 'JJ' and so on for the previous questions.

Some more thought shows that you can always come up
with *some* question that fits whatever choice of
outcomes you want, given the constraints above. So
we have a lot of freedom to choose the outcomes in
the above table, the only problem will be to think
of the corresponding verbal questions.

So the first problem is to come up with some question
which would be answered as in the '1st' column.
This question could be, using the idea of Jesse Mazer,
but with an extra trick:
"If I asked you "Is the 2nd God the 'R'", would
you say 'JA'?"
The interesting thing is that this question does not
tell us if JA is YES or NO, but a minute of thought
shows that the outcomes are the same whatever JA means.

After some thought, the other questions can be:
Column'J': "3rd god, if I asked you 'Are you the 'F'',
would you say 'JA'?";
Column'D': "2nd god, if I asked you 'Are you the 'F'',
would you say 'JA'?";
Columns 'JJ' and 'JD': "3rd god, if I asked you
'Is the 2nd god 'R'', would you say 'JA'?";
Columns 'DJ' and 'DD': "2nd god, if I asked you
'Is the 3rd god 'R'', would you say 'JA'?".

So I think these would solve the problem. It was a
lot of fun! Let me see what you guys think.

As an extra challenge, can you think of a way to
find out if JA=YES in some of the outcomes? It
would involve different questions, but I think it
should be possible in principle.

Eric.
Received on Tue Oct 12 2004 - 22:18:59 PDT