\documentstyle[fullpage]{article}
\begin{document}
\begin{center}
{\bf The Hardest Logic Puzzle in the World}

\bigskip
You are faced with three gods.  You know that they are, in no
particular order, the God of Truth, who always speaks the truth, the
God of Falsity, who always lies, and the God of Diplomacy, whose
answers cannot be predicted in any way.  You must determine who they
are by asking three yes or no questions.  The Gods' answers will be
either ``ya'' or ``da''; one of those words means ``yes'' and the
other means ``no,'' but you don't know which is which.
\end{center}
\bigskip
At first glance, this problem appears provably unsolvable: there are
six possible configurations of the gods (more than two bits of
information), and there is no way to guarantee that your first
question provides any information (since Random's answers do not
convey any meaning).  However, even though Random's {\em answers} do
not convey any meaning, the idea that a particular god is Random is
enough to narrow down the number of possible configurations to two
(one bit).

So the problem may be solvable.  Let us first see what tools we have
available.  First, we can give the gods temporary names A, B, and C.
(Presumably, when we actually talk to the gods, we will have to talk
about ``the god on my left'' or ``the middle god'', but such
translations have nothing to do with logic.)  Second, we can note that
Truth and Falsity are essentially equivalent, except that they use
opposite values of ``ya'' and ``da'' to represent ``yes'' and ``no.''

Third, even though we don't know (and, if we're clever, don't care)
whether ``ya'' means ``yes'' or ``no,'' we can still get definition
information out of either Truth or Falsity, without knowing which is
which.  Our questions will be of the form, ``If I were to ask you if X
is true, would your answer be `ya'?''  It is a simple exercise to show
that, regardless of whether our questionee is Truth or Falsity, the
answer will be ``ya'' if X is true and ``da'' if X is false:

\begin{center}
\begin{tabular}{ccccc}
X&Questionee&Meaning of ``ya''&Answer to ``is X true?''&Answer to question\\
\hline\\
T & Truth & Yes & ya (yes) & ya (yes) \\
T & Truth & No & da (yes) & ya (no) \\
T & Falsity & Yes & da (no) & ya (yes) \\
T & Falsity & No & ya (no) & ya (no) \\
F & Truth & Yes & da (no) & da (no) \\
F & Truth & No & ya (no) & da (yes) \\
F & Falsity & Yes & ya (yes) & da (no) \\
F & Falsity & No & da (yes) & da (yes) \\
\end{tabular}
\end{center}

Okay.  So we can get straight answers out of Truth and Falsity.  This
doesn't help us with Random, whose answers convey no information.  The
answers we get will thus be either, ``Either I am Random, or X is
true'' or ``Either I am Random, or X is false''.

Now that we've determined how to use this tool, we will abstract it
away.  For the remainder of the solution, I will talk about asking a
god ``Is X true?'' and receiving an answer ``yes'' or ``no'', where
``yes'' tells us ``I am Random or X is true'' and ``no'' tells us ``I
am Random or X is false''.

From here, it's a question of who we should ask questions, and what
``X'' should be.  We can try out sample questions, like asking A ``are
you Truth?'', which gives us the result ``A is Random or A is truth''
(if the answer is ``yes'') or ``A is Random or A is falsity'' (if the
answer is ``no'').  Each of these results narrows down the field to
four possibilities, which is okay, since we have two more questions.
In fact, any question narrows the field to four possibilities.

The second question must narrow the field to two possibilities,
regardless of the answer.  After some experimentation, we determine
that it is impossible to narrow the field from four possibilities to
two if the god we question has any chance of being Random: regardless
of whether the answer is ``yes'' or ``no'', the god could be Random
(and we have no other new information).  Thus there is at least one
possibility that remains in both the case where the answer is ``yes''
and the case where the answer is ``no'', and regardless of where the
remaining three cases fall, one or both cases will leave open three
possibilities.

So the first question must be enough for us to find a god who is not
Random, or we are out of luck.  We can do this by asking A, ``Is B
Random?''  If the answer is yes, then either A or B is Random and C is
not; if the answer is no, then either B is not Random, or A is Random
(and B is not).  Now the problem is simple; we have four possibilities
left, and we have a god from whom we can get yes-or-no answers.  For
example, suppose the answer to the first question is ``no'', meaning
either A or C is Random and B is not.  (If the answer to the first
question is ``yes,'' then we are in the same sitution with B and C
reversed.)  We ask B: ``Is A Random?''.  If the answer is yes, then we
ask B ``Is B Truth?'' to determine if A or B is truth.  If the answer
is no (A is not Random), then C is Random and we ask ``Is B Truth?''
to determine whether A or B is truth.

\end{document}

