
\documentstyle{article}

\begin{document}

\sloppy

\section{Problem}

     Our dauntless hero re-entered the megasphere.  ``Back to Earth at
last!'' he radioed.  ``By the way, I have captured four Zuknugs.  They
have to obey me, since I alone can land the spaceship.  They are
part little-green-men and part bug-eyed-monsters.  And yes, during
our 20 years cooped up in here I have managed to teach them English.

     ``However, before the press gets hold of them I had better warn
you that what Guj says is always true and what Kiq says is never true.
Thog and Thag are brothers, and the one you question first will choose
between true and false at random, but then his brother will choose the
opposite.  And now for the landing!  No time to tell you any more!''.

     In due course the astronaut stepped out on Earth but at that moment
a long green tentacle reached out through the door and strangled him.

     The obvious person to put in charge of the case was me.

     I thrust the slimy horrors into four cages marked Alf, Bert, Joe
and Fred.

     ``Tell me, Alf.  If I ask Joe for Bert's real name, what will Joe
say?''
     ``Guj.''

     ``And now you, Bert.  Are you one of the two brothers?''
     ``No.''

     ``Your turn, Joe.  Which brother will I have questioned first?''
     ``Thog.''

     ``And lastly Fred.  What is your real name?''
     ``Guj.''

     I closed my notebook.  ``Right.  That will be all for now.''  I pointed
to each one in turn.  ``You are Guj, you are Kiq, you are Thog, and you
are Thag.''

     Unless the astronaut was mistaken, I had to be right.
Can you name them? (From {\em The Times}, 29/12/91, p26,
attributed to Denis Young.)

\section{Solution}

Instead solve a slightly simpler problem in which the four questioned
(but not the questioner) know in advance how Thog and Thag will behave.
The universe $S$ is the set of permutation sequences of the
name set
$N:\{$`Guj', `Kiq', `Thog', `Thag'$\}$.
Elements $0, 1, 2, 3$ of a particular permutation correspond to 
`Alf', `Bert', `Joe' and `Fred' respectively.
Define the ``truth-functions''
\begin{eqnarray*}
\Phi_X (Q) & = & \left\{
			 \begin{array}{ll}
			 Q,  & X \in \{\mbox{`Guj'}, \mbox{`Thog'}\} \\
			 \neg Q, & X \in \{\mbox{`Kiq'}, \mbox{`Thag'}\}
			 \end{array}
		 \right. \\
{\overline{\Phi}}_X (Q) & = & \left\{
			 \begin{array}{ll}
			 Q,  & X \in \{\mbox{`Guj'}, \mbox{`Thag'}\} \\
			 \neg Q, & X \in \{\mbox{`Kiq'}, \mbox{`Thog'}\}
			 \end{array}
		 \right. .
\end{eqnarray*}
$\Phi$ will be applicable if Thog is telling the truth and Thag is lying,
$\overline{\Phi}$ if Thag is telling the truth and Thog is lying.
In the former case the responses to the four questions translate
to the following conjunction concerning the permutation $P$
\begin{eqnarray*}
R (P) & = & (\forall Y:N \cdot \Phi_{P_2} (P_1 = Y) \Rightarrow \Phi_{P_0} (Y = \mbox{`Guj'})) \wedge \\
      &   & \Phi_{P_1} (\neg ((P_1 = \mbox{`Thog'}) \vee (P_1 = \mbox{`Thag'}))) \wedge \\
      &   & \Phi_{P_2} ((P \left\lceil \{\mbox{`Thog'},\mbox{`Thag'}\} \right. )_0 = \mbox{`Thog'}) \wedge \\
      &   & \Phi_{P_3} (P_3 = \mbox{`Guj'}).
\end{eqnarray*}
The notation $P \left\lceil \sigma \right.$ is used to represent the sequence
obtained from $P$ by deleting all values {\em not} in the set $\sigma$, so
$(P \left\lceil \sigma \right.)_0$ is the value of the first instance of any element
of $\sigma$ (used for transcribing the third question). $\overline{R}$ is
defined by replacing $\Phi $ by $\overline{\Phi}$ in the expression above.
Now, show
\begin{displaymath}
\exists P:S \cdot R (P) \vee \overline{R} (P).
\end{displaymath}

\end{document}
