1 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 The Times, 29/12/91, p26, attributed to Denis Young.)

2 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”

Φ_{X}(Q) = \{ \begin{matrix}Q, & X ∈ \{‘Guj’, ‘Thog’\} \\ ¬Q, & X ∈ \{‘Kiq’, ‘Thag’\} \end{matrix}
\overline{Φ}_{X}(Q) = \{ \begin{matrix}Q, & X ∈ \{‘Guj’, ‘Thag’\} \\ ¬Q, & X ∈ \{‘Kiq’, ‘Thog’\} \end{matrix} .

Φ will be applicable if Thog is telling the truth and Thag is lying, \overline{Φ} 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

R(P) = (∀Y : N · Φ_{P_{2}}(P_{1} = Y) ⇒ Φ_{P_{0}}(Y = ‘Guj’)) ∧

Φ_{P_{1}}(¬((P_{1} = ‘Thog’) ∨ (P_{1} = ‘Thag’))) ∧
Φ_{P_{2}}((P ⌈{‘Thog’, ‘Thag’})_{0} = ‘Thog’) ∧
Φ_{P_{3}}(P_{3} = ‘Guj’).

The notation P ⌈σ is used to represent the sequence obtained from P by deleting all values not in the set σ, so (P ⌈σ)_{0} is the value of the first instance of any element of σ (used for transcribing the third question). \overline{R} is defined by replacing Φ by \overline{Φ} in the expression above. Now, show

∃P : S · R(P) ∨ \overline{R}(P).