# How to Solve "The Hardest Logic Puzzle Ever" and Its Generalization

Daniel Vallstrom

(March 2022)

###### Abstract

Raymond Smullyan came up with a puzzle that George Boolos called “The Hardest
Logic Puzzle Ever”.[1] The puzzle has truthful, lying, and random gods who
answer yes or no questions with words that we don’t know the meaning of. The
challenge is to figure out which type each god is. The puzzle has attracted
some general attention — for example, one popular presentation of the puzzle
has been viewed 10 million times.[2] Various “top-down” solutions to the
puzzle have been developed.[1, 3] Here a systematic bottom-up approach to the
puzzle and its generalization is presented. We prove that an $n$ gods puzzle
is solvable if and only if the random gods are less than the non-random gods.
We develop a solution using $4.15$ questions to the $5$ gods variant with $2$
random and $3$ lying gods.

There is also an aside on mathematical vs. computational thinking.

## 1 The hardest logic puzzle ever

######  Definition 1.1 (The Hardest Logic Puzzle Ever).

Three gods ($\gamma_{1},\ldots,\gamma_{3}$) will answer three yes or no
questions. Each question is to be directed at one god at a time. The gods
answer with the word ‘$\chi$’ (or ‘_’) but we don’t know what ‘$\chi$’ (or
‘_’) means. One god ($\mathcal{T}$) always tells the truth, one
($\mathcal{F}$) always lies, and one ($\mathcal{R}$) answers randomly111The
puzzle has been interpreted as to allow for the random god to not answer
randomly but instead randomly function as a god who either tells the truth, or
lies.[4] Since this renders the random god pointless, we’ll stick to the
interpretation that the random god answers truly randomly. Besides, the truly
random interpretation seems to be what Boolos had in mind,[1] e.g. with
explanations like “will answer your question yes or no, completely at
random”[1, p. 2]. It is also how [3] interpreted the puzzle.. The challenge is
to figure out which god is which.[1]

## 2 Groundwork

We’ll use $0$, $\bot$, no, and false interchangeably, when there is no risk
for confusion. And similarly for $1$, $\top$, yes, and true. And $\chi$,
whatever it means. We’ll also e.g. use ’$=$’ as a boolean function.

With $3$ gods there are $3\cdot 2$ possibilities for the gods. This doubles if
we are to figure out the meaning of $\chi$. With $3$ questions we can discern
$2^{3}$ outcomes. Hence, we better remain ignorant of the meaning of $\chi$.

### 2.1 A question template

Let $\gamma(q)$ be god $\gamma$’s answer to the question $q$.

Given a yes or no question $q$, and a god $\gamma$, we want a function
$t(q,\gamma,\chi)\rightarrow\left\\{0,1\right\\}$ that gives the truth value
of $q$ when $\gamma$ isn’t the random god.

Fortunately, one of the first and simplest attempts at such a $t$ yields one
that works:

######  Definition 2.1.

$t(q,\gamma)\coloneqq\;\;\gamma(\mbox{``}\gamma(q)=\chi\mbox{''})=\chi$

######  Theorem 2.2.

If $\gamma\neq\mathcal{R}$, then $t(q,\gamma)\leftrightarrow q$

###### Proof.

We’ll go through all possible cases:

$\bm{q\\!=\\!1,\gamma\\!=\\!\mathcal{T},\chi\\!=\\!1}$:

Then $\gamma(q)\\!=\\!\chi$, and
$\gamma(\mbox{``}\gamma(q)\\!=\\!\chi\mbox{''})\\!=\\!\chi$.

$\bm{q\\!=\\!1,\gamma\\!=\\!\mathcal{T},\chi\\!=\\!0}$:

Then $\gamma(q)\\!\neq\\!\chi$, and
$\gamma(\mbox{``}\gamma(q)\\!=\\!\chi\mbox{''})\\!=\\!\chi$.

$\bm{q\\!=\\!1,\gamma\\!=\\!\mathcal{F},\chi\\!=\\!1}$:

Then $\gamma(q)\\!\neq\\!\chi$, and
$\gamma(\mbox{``}\gamma(q)\\!=\\!\chi\mbox{''})\\!=\\!\chi$.

$\bm{q\\!=\\!1,\gamma\\!=\\!\mathcal{F},\chi\\!=\\!0}$:

Then $\gamma(q)\\!=\\!\chi$, and
$\gamma(\mbox{``}\gamma(q)\\!=\\!\chi\mbox{''})\\!=\\!\chi$.

$\bm{q\\!=\\!0,\gamma\\!=\\!\mathcal{T},\chi\\!=\\!1}$:

Then $\gamma(q)\\!\neq\\!\chi$, and
$\gamma(\mbox{``}\gamma(q)\\!=\\!\chi\mbox{''})\\!\neq\\!\chi$.

$\bm{q\\!=\\!0,\gamma\\!=\\!\mathcal{T},\chi\\!=\\!0}$:

Then $\gamma(q)\\!=\\!\chi$, and
$\gamma(\mbox{``}\gamma(q)\\!=\\!\chi\mbox{''})\\!\neq\\!\chi$.

$\bm{q\\!=\\!0,\gamma\\!=\\!\mathcal{F},\chi\\!=\\!1}$:

Then $\gamma(q)\\!=\\!\chi$, and
$\gamma(\mbox{``}\gamma(q)\\!=\\!\chi\mbox{''})\\!\neq\\!\chi$.

$\bm{q\\!=\\!0,\gamma\\!=\\!\mathcal{F},\chi\\!=\\!0}$:

Then $\gamma(q)\\!\neq\\!\chi$, and
$\gamma(\mbox{``}\gamma(q)\\!=\\!\chi\mbox{''})\\!\neq\\!\chi$.

(Cases also hold for symmetry reasons, and for double negation reasons.) ∎

For convenience we’ll also introduce a way to refer to the meta-question put
to the god in definition 2.1:

######  Definition 2.3.

$t_{q}(q,\gamma)\coloneqq\;\;\mbox{``}\gamma(q)=\chi\mbox{''}$

Boolos does not use something like definition 2.3 in his solution to the
puzzle,[1] but Tim Roberts does.[3]

### 2.2 How to find questions

Instead of presenting “top-down” solutions, we’ll try to develop solutions
from the ground up, that are guaranteed to work, and are optimal.

Essential for efficient searches is to split the search space in equally large
subparts. This means that we want the possible answers to a question to be
equally strong.

#### 2.2.1 Finding a solution to the non-random interpretation

Let’s suppose, as preparation, that $\mathcal{R}$ functions like either
$\mathcal{T}$ or $\mathcal{F}$ (cf. fn. 1); in particular, theorem 2.2 works
also for $\mathcal{R}$.

Then an optimal split of the $6$ possibilities would be provided by asking
about:

######  Definition 2.4 ($q_{\bar{\mathcal{R}}}$).

$q_{\bar{\mathcal{R}}}\coloneqq\;\;\bigvee\left\\{\begin{matrix}\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{F}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{F},\gamma_{3}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{F},\gamma_{3}=\mathcal{R}\\}\;\\\
\end{matrix}\right\\}$ (1)

We’ll also need to reason about $\neg q_{\bar{\mathcal{R}}}$.

$\neg
q_{\bar{\mathcal{R}}}\leftrightarrow\bigwedge\left\\{\begin{matrix}\lor\\{\gamma_{1}\neq\mathcal{R},\gamma_{2}\neq\mathcal{T},\gamma_{3}\neq\mathcal{F}\\},\\\
\lor\\{\gamma_{1}\neq\mathcal{R},\gamma_{2}\neq\mathcal{F},\gamma_{3}\neq\mathcal{T}\\},\\\
\lor\\{\gamma_{1}\neq\mathcal{T},\gamma_{2}\neq\mathcal{F},\gamma_{3}\neq\mathcal{R}\\}\;\\\
\end{matrix}\right\\}$ (2)

which in disjunctive normal form (DNF) becomes

$\neg
q_{\bar{\mathcal{R}}}\leftrightarrow\bigvee\left\\{\begin{matrix}\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{F}\\},\\\
\land\\{\gamma_{1}=\mathcal{F},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R}\\},\\\
\land\\{\gamma_{1}=\mathcal{F},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{T}\\}\;\\\
\end{matrix}\right\\}$ (3)

######  Solution 2.5.

There is a solution to the non-random interpretation of “The Hardest Logic
Puzzle Ever” using $2.67$ questions. (It’s also enough to assume non-
randomness for only the first question.)

###### Proof.

Put $t_{q}(q_{\bar{\mathcal{R}}},\gamma_{1})$ to $\gamma_{1}$ and consider the
possible cases:

Case $t(q_{\bar{\mathcal{R}}},\gamma_{1})$:

Then we know from theorem 2.2, and from the supposed non-randomness of
$\mathcal{R}$, that $q_{\bar{\mathcal{R}}}$ holds. Next we’ll ask $\gamma_{2}$
about $\gamma_{2}=\mathcal{T}$.

Suppose $t(\gamma_{2}=\mathcal{T},\gamma_{2})$.

Then we know from equation (1) that $\gamma_{1}=\mathcal{R}$,
$\gamma_{2}=\mathcal{T}$, and $\gamma_{3}=\mathcal{F}$.

This case used $2$ questions.

Suppose $\neg t(\gamma_{2}=\mathcal{T},\gamma_{2})$.

Then we know from equation (1) that $\gamma_{2}=F$.

$t(\gamma_{1}=\mathcal{T},\gamma_{2})$ determines which is which of
$\gamma_{1}$ and $\gamma_{3}$.

Case $\neg t(q_{\bar{\mathcal{R}}},\gamma_{1})$:

Then $\neg q_{\bar{\mathcal{R}}}$. Next we’ll ask $\gamma_{1}$ about
$\gamma_{1}=\mathcal{T}$.

Suppose $t(\gamma_{1}=\mathcal{T},\gamma_{1})$.

Then we know from equation (3) that $\gamma_{1}=\mathcal{T}$,
$\gamma_{2}=\mathcal{R}$, and $\gamma_{3}=\mathcal{F}$.

This case used $2$ questions.

Suppose $\neg t(\gamma_{1}=\mathcal{T},\gamma_{1})$.

Then we know from equation (3) that $\gamma_{1}=F$.

$t(\gamma_{2}=\mathcal{T},\gamma_{1})$ determines which is which of
$\gamma_{2}$ and $\gamma_{3}$.

∎

#### 2.2.2 Managing randomness

For the full version of the puzzle (def. 1.1), each question that can be
answered by the random god weakens the narrowing of the search space by up to
$2$ possibilities, adding
$(\gamma_{1}\\!=\\!\mathcal{R},\gamma_{2}\\!=\\!\mathcal{F},\gamma_{3}\\!=\\!\mathcal{T})$
and
$(\gamma_{1}\\!=\\!\mathcal{R},\gamma_{2}\\!=\\!\mathcal{T},\gamma_{3}\\!=\\!\mathcal{F})$
to the list of possibilities, say. So it also seems important to find, as
quickly as possible, a god that isn’t $\mathcal{R}$, in order to get reliable
answers and minimize waste.

Hence, the problem with asking about something like $q_{\bar{\mathcal{R}}}$
for the full puzzle (def. 1.1) is that the conclusion we are able to draw from
$\neg t(q_{\bar{\mathcal{R}}},\gamma_{1})$ is given by

$\bigvee\left\\{\begin{matrix}\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{F}\\},\\\
\land\\{\gamma_{1}=\mathcal{F},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R}\\},\\\
\land\\{\gamma_{1}=\mathcal{F},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{F},\gamma_{3}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{F}\\}\;\\\
\end{matrix}\right\\}$

Since this has $5$ possibilities, it’s not solvable with only the remaining
$2$ questions. (The case $t(q_{\bar{\mathcal{R}}},\gamma_{1})$ remains as in
solution 2.5 though as that case already includes the possibilities
$(\mathcal{R},\mathcal{F},\mathcal{T})$ and
$(\mathcal{R},\mathcal{T},\mathcal{F})$.)

Instead we’ll again balance the partitions, by moving $1$ of the added random
possibilities from the negative side to the positive:

######  Definition 2.6 ($q_{1}$).

$q_{1}\coloneqq\;\;\bigvee\left\\{\begin{matrix}\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{F}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{F},\gamma_{3}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{F},\gamma_{3}=\mathcal{R}\\},\\\
\land\\{\gamma_{1}=\mathcal{F},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R}\\}\;\\\
\end{matrix}\right\\}$ (4)

We’ll also need to reason about $\neg q_{1}$.

$\neg
q_{1}\leftrightarrow\bigwedge\left\\{\begin{matrix}\lor\\{\gamma_{1}\neq\mathcal{R},\gamma_{2}\neq\mathcal{T},\gamma_{3}\neq\mathcal{F}\\},\\\
\lor\\{\gamma_{1}\neq\mathcal{R},\gamma_{2}\neq\mathcal{F},\gamma_{3}\neq\mathcal{T}\\},\\\
\lor\\{\gamma_{1}\neq\mathcal{T},\gamma_{2}\neq\mathcal{F},\gamma_{3}\neq\mathcal{R}\\},\\\
\lor\\{\gamma_{1}\neq\mathcal{F},\gamma_{2}\neq\mathcal{T},\gamma_{3}\neq\mathcal{R}\\}\;\\\
\end{matrix}\right\\}$ (5)

which in disjunctive normal form becomes

$\neg
q_{1}\leftrightarrow\bigvee\left\\{\begin{matrix}\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{F}\\},\\\
\land\\{\gamma_{1}=\mathcal{F},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{T}\\}\;\\\
\end{matrix}\right\\}$ (6)

which with added $\mathcal{R}$ possibilities gives

######  Definition 2.7 ($\bar{q}_{1}^{R}$).

$\bar{q}_{1}^{R}\coloneqq\;\;\bigvee\left\\{\begin{matrix}\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{F}\\},\\\
\land\\{\gamma_{1}=\mathcal{F},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{F},\gamma_{3}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{F}\\}\;\\\
\end{matrix}\right\\}$ (7)

## 3 A bottom-up solution to the puzzle

######  Solution 3.1.

A solution to “The Hardest Logic Puzzle Ever” exists.

###### Proof.

Put $t_{q}(q_{1},\gamma_{1})$ to $\gamma_{1}$ and consider the possible cases:

Case $t(q_{1},\gamma_{1})$:

Since equation (4) already includes all the possibilities where
$\gamma_{1}=\mathcal{R}$, $q_{1}$ holds. Hence $\gamma_{2}\neq\mathcal{R}$ and
is safe to question.

Next we’ll ask $\gamma_{2}$ about $\gamma_{2}=\mathcal{T}$.

After that, $t(\gamma_{1}=\mathcal{R},\gamma_{2})$ determines which is which
of $\gamma_{1}$ and $\gamma_{3}$.

Case $\neg t(q_{1},\gamma_{1})$:

Then $\gamma_{1}=\mathcal{R}$ or $\neg q_{1}$ holds. Adding the
$\gamma_{1}=\mathcal{R}$ possibilities to $\neg q_{1}$ results in
$\bar{q}_{1}^{R}$, which must hold. Inspecting equation (7) shows that
$\gamma_{3}\neq\mathcal{R}$ and is safe to question.

Next we’ll ask $\gamma_{3}$ about $\gamma_{3}=\mathcal{T}$.

After that, $t(\gamma_{1}=\mathcal{R},\gamma_{3})$ determines which is which
of $\gamma_{1}$ and $\gamma_{2}$.

∎

Note that $q_{1}\leftrightarrow(\gamma_{2}\\!\neq\\!\mathcal{R})$. A first
question $q$ such that $q$ and $\neg q$ are equally strong, and where equally
many $\mathcal{R}$ possibilities are added to each side of the search split,
works too — for example
$\gamma_{3}\\!=\\!\mathcal{R}\lor(\gamma_{1}\\!=\\!\mathcal{R}\land\gamma_{2}\\!=\\!\mathcal{T}\land\gamma_{3}\\!=\\!\mathcal{F})$.

Note too that there is no solution using less than $3$ questions to the full
puzzle.

## 4 The n gods puzzle class

######  Definition 4.1 (The Hardest Logic Puzzle Ever with $n$ Gods, $m$
Random Gods, and $k$ Truthfull Gods).

Let the $(n,m,k)$ gods puzzle be like “The Hardest Puzzle Ever” (def. 1.1) but
with $n$ gods, $m$ random gods, $k$ truthful gods, $n-m-k$ lying gods, and
with no restriction on the number of questions allowed.

######  Theorem 4.2.

An $n$ gods puzzle is solvable if and only if the number of random gods is
stricly less than the number of non-random gods.

######  Lemma 4.3.

If an $n$ gods puzzle has strictly more non-random gods than random gods, then
a non-random god can be found.

###### Proof.

We’ll prove the lemma by induction.

The lemma holds for puzzles with $1$ and $2$ gods.

Assume that the lemma holds for $k<n$, and that there are more non-random gods
than random gods. We’ll then find a non-random god for the $n$ case.

Ask $\gamma_{1}$ about $\gamma_{i}\\!=\\!\mathcal{R}$ for $2\leq i\leq n$
until $t(\gamma_{i}\\!=\\!\mathcal{R},\gamma_{1})$, or all gods have been
checked.

If $\gamma_{1}\\!\neq\\!\mathcal{R}$, then $\gamma_{i}\\!=\\!\mathcal{R}$ by
theorem 2.2, or there are no more random gods at all.

Hence, the subproblem for
$(\gamma_{2},\ldots,\gamma_{i-1},\gamma_{i+1},\linebreak[1]\ldots,\linebreak[1]\gamma_{n})$
has at least $1$ less random god, and at most $1$ less non-random god, if
there is any random god at all. Thus, a non-random god $\gamma_{j}$ can be
found for the subproblem. And $\gamma_{j}$ suffice for the $n$ case too. ∎

######  Lemma 4.4.

If an $n$ gods puzzle has strictly more non-random gods than random gods, then
it is solvable.

###### Proof.

Assume more non-random gods than random gods. Then, by lemma 4.3, a non-random
god $\gamma_{j}$ can be found. After that it’s straightforward to go through
all gods and ask $\gamma_{j}$ about their identity. This determines all the
gods, according to theorem 2.2. ∎

###### Proof of theorem 4.2.

The $\Leftarrow$ case is covered by lemma 4.4.

For the $\Rightarrow$ case, to see why puzzles with at least as many random
gods as non-random gods aren’t solvable, consider the easiest to solve of such
problems: Assume that $n$ is even, that the random gods equal the non-random
gods, and that there are only truthful non-random gods. Let

######  Definition 4.5.

$p_{n}\coloneqq$

$\bigvee\\!\\!\left\\{\begin{matrix}\land\\{\gamma_{1}\\!=\\!\mathcal{T},\gamma_{2}\\!=\\!\mathcal{R},\gamma_{3}\\!=\\!\mathcal{T},\gamma_{4}\\!=\\!\mathcal{R},\ldots,\gamma_{n}\\!=\\!\mathcal{R}\\},\\\
\land\\{\gamma_{1}\\!=\\!\mathcal{R},\gamma_{2}\\!=\\!\mathcal{T},\gamma_{3}\\!=\\!\mathcal{R},\gamma_{4}\\!=\\!\mathcal{T},\ldots,\gamma_{n}\\!=\\!\mathcal{T}\\}\;\\\
\end{matrix}\\!\right\\}\\!\\!$ (8)

Let $p_{\mathcal{\scriptscriptstyle T}\mathcal{\scriptscriptstyle R}}$ and
$p_{\mathcal{\scriptscriptstyle R}\mathcal{\scriptscriptstyle T}}$ be the
conjunctions of $p_{n}$:

######  Definition 4.6.

$p_{\mathcal{\scriptscriptstyle T}\mathcal{\scriptscriptstyle R}}\coloneqq$

$\land\\{\gamma_{1}\\!=\\!\mathcal{T},\gamma_{2}\\!=\\!\mathcal{R},\gamma_{3}\\!=\\!\mathcal{T},\gamma_{4}\\!=\\!\mathcal{R},\ldots,\gamma_{n}\\!=\\!\mathcal{R}\\}$
(9)

######  Definition 4.7.

$p_{\mathcal{\scriptscriptstyle R}\mathcal{\scriptscriptstyle T}}\coloneqq$

$\hskip
30.00005pt\land\\{\gamma_{1}\\!=\\!\mathcal{R},\gamma_{2}\\!=\\!\mathcal{T},\gamma_{3}\\!=\\!\mathcal{R},\gamma_{4}\\!=\\!\mathcal{T},\ldots,\gamma_{n}\\!=\\!\mathcal{T}\\}$
(10)

If the gods are as described by $p_{\mathcal{\scriptscriptstyle
T}\mathcal{\scriptscriptstyle R}}$ or $p_{\mathcal{\scriptscriptstyle
R}\mathcal{\scriptscriptstyle T}}$, and only $p_{n}$ is known, then that
puzzle instance is unsolvable, if the random gods are unhelpful (we’ll show
this next). So let’s assume that the gods are as described by $p_{n}$.

To get to an unsolvable position, we’ll have the random gods “happen” to force
the puzzle there. To that end, if both $q$ and $\neg q$ are consistent with
$p_{n}$, (i.e. not $p_{n}\\!\rightarrow\\!\neg q$ and not
$p_{n}\\!\rightarrow\\!q$), assume that the random gods always happen to give
the incorrect answer to a question about $q$. If only one of $q$ and $\neg q$
is consistent with $p_{n}$, assume that the random gods always happen to give
the correct answer to a question about $q$.

Call a question ‘trivial’ if it or its negation follow from already asked
questions.

Given this setup, and if non-trivial questions are asked, then it will be
known that $p_{n}$ holds. But once there, no more conclusion can be drawn from
the answer to a question $q$. And it is not possible to determine which of
$p_{\mathcal{\scriptscriptstyle T}\mathcal{\scriptscriptstyle R}}$ and
$p_{\mathcal{\scriptscriptstyle R}\mathcal{\scriptscriptstyle T}}$ that holds.

More specifically, without loss of generality we will assume that $\gamma_{1}$
is asked about $q$.

An easy way to see that we are able to conclude $p_{n}$ is to note that we can
ask $\frac{n}{2}+1$ gods about $p_{n}$ explicitly. Since all gods answer that
$p_{n}$ holds, $p_{n}$ can be concluded since at least $1$ of $\frac{n}{2}+1$
gods must be non-random.

Note that if $p_{n}$ is known and $q$ is non-trivial, then $q\leftrightarrow
p_{\mathcal{\scriptscriptstyle T}\mathcal{\scriptscriptstyle R}}$ or
$q\leftrightarrow p_{\mathcal{\scriptscriptstyle R}\mathcal{\scriptscriptstyle
T}}$. Because suppose that $q$ is non-trivial. Then it has a model
$\mathcal{M}$ (i.e. an assignment of the gods) where $q$, and $p_{n}$, are
true. Suppose, without loss of generality, that it’s the
$p_{\mathcal{\scriptscriptstyle T}\mathcal{\scriptscriptstyle R}}$ disjunct
that’s true in $\mathcal{M}$. Then, since $p_{\mathcal{\scriptscriptstyle
T}\mathcal{\scriptscriptstyle R}}$ completely determines a model, $q$ holds
whenever $p_{\mathcal{\scriptscriptstyle T}\mathcal{\scriptscriptstyle R}}$
does, i.e. $p_{\mathcal{\scriptscriptstyle T}\mathcal{\scriptscriptstyle
R}}\rightarrow q$. Suppose $\neg p_{\mathcal{\scriptscriptstyle
T}\mathcal{\scriptscriptstyle R}}$. Then $p_{\mathcal{\scriptscriptstyle
R}\mathcal{\scriptscriptstyle T}}$. Since $p_{\mathcal{\scriptscriptstyle
R}\mathcal{\scriptscriptstyle T}}$ determines its models completely, if $q$
where to hold, then $q$ would hold in all models to $p_{n}$, contradicting
that $q$ is non-trivial. Hence $\neg q$ holds, i.e. $\neg
p_{\mathcal{\scriptscriptstyle T}\mathcal{\scriptscriptstyle
R}}\rightarrow\neg q$.

Assume that $p_{n}$ is known. To see that once $p_{n}$ is known, no more
conclusions can be made, suppose $\gamma_{1}\\!=\\!\mathcal{T}$, and $q$ is
non-trivial. Then an answer that $q$ (or $\neg q$) holds (with implications
that $p_{\mathcal{\scriptscriptstyle T}\mathcal{\scriptscriptstyle R}}$ holds)
is undone because we can only conclude that
$q\vee\gamma_{1}\\!=\\!\mathcal{R}$ (or $\neg
q\vee\gamma_{1}\\!=\\!\mathcal{R}$), which is equivalent to $p_{n}$.

Similarly, if instead $\gamma_{1}=\mathcal{R}$, then we are able to conclude
only $q\vee\gamma_{1}\\!=\\!\mathcal{R}$ (or $\neg
q\vee\gamma_{1}\\!=\\!\mathcal{R}$). If $q$ is non-trivial, then both $q$ and
$\neg q$ are consistent with $p_{n}$. Hence, the false answer that $q$ (or
$\neg q$) holds undoes the disjunct $\gamma_{1}=\mathcal{R}$.

If $q$ is trivial, the concluded disjunction,
$q\vee\gamma_{1}\\!=\\!\mathcal{R}$ (or $\neg
q\vee\gamma_{1}\\!=\\!\mathcal{R}$), will already be known, and nothing new
can be concluded again.

To see that even harder puzzles to solve are unsolvable too, the restriction
that the non-random gods are only truthful is immaterial.

If more random gods are added, the proof still works with minor alterations,
e.g. to eq. (8). ∎

## 5 A solution to the 5 gods puzzle with 2 random and 3 truthful gods

We will solve the puzzle where the non-random gods are the same (i.e. all
$\mathcal{T}$, or all $\mathcal{F}$). This is unimportant although it reduces
the number of possibilities; the other variants are similar.

There are $\frac{5\cdot 4}{2}$ possibilities for the gods.

We’ll address $\gamma_{1}$ first, without loss of generality.

Included in any conclusions drawn from the first answer is that $\gamma_{1}$
could be $\mathcal{R}$: $\gamma_{1}\\!=\\!\mathcal{R}\;\leftrightarrow$

$\bigvee\\!\\!\left\\{\\!\begin{matrix}\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{R}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{R},\gamma_{5}=\mathcal{T}\\},\vspace{0pt}\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\}\;\\\
\end{matrix}\\!\right\\}\\!\\!\\!\\!$ (11)

For the first question we’ll take half of the conjunctions from
$\gamma_{1}=\mathcal{R}$ (eq. (11)), and add half of the remaining
possibilities, aiming to get $\gamma_{2}$ likely to be non-random in the
positive case, and $\gamma_{3}$ likely non-random in the negative case:

######  Definition 5.1.

$q_{1}^{5}\coloneqq$

$\bigvee\\!\left\\{\\!\begin{matrix}\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{R}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{R},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{R},\gamma_{5}=\mathcal{R}\\},\vspace{0pt}\\\
\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{R}\\},\\\
\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{R},\gamma_{5}=\mathcal{T}\\}\;\\\
\end{matrix}\\!\right\\}\\!\\!\\!$ (12)

We’ll also need to reason about $\neg q_{1}^{5}$. Using disjunctive normal
form we have: $\neg q_{1}^{5}\leftrightarrow$

$\bigvee\\!\\!\left\\{\\!\begin{matrix}\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{R}\\},\\\
\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{R},\gamma_{5}=\mathcal{T}\\},\vspace{0pt}\\\
\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\}\;\\\
\end{matrix}\\!\right\\}\\!\\!\\!$ (13)

Adding $\gamma_{1}=\mathcal{R}$ possibilities (eq. (11)) to $q_{1}^{5}$ and
$\neg q_{1}^{5}$ gives

######  Definition 5.2.

$q_{15}^{R}\coloneqq$

$\bigvee\\!\\!\left\\{\\!\begin{matrix}\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{R}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{R},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{R},\gamma_{5}=\mathcal{R}\\},\vspace{0pt}\\\
\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{R}\\},\\\
\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{R},\gamma_{5}=\mathcal{T}\\}\;\\\
\end{matrix}\\!\right\\}\\!\\!$ (14)

######  Definition 5.3.

$\bar{q}_{15}^{R}\coloneqq$

$\bigvee\\!\\!\left\\{\\!\begin{matrix}\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{R}\\},\\\
\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{R},\gamma_{5}=\mathcal{T}\\},\vspace{0pt}\\\
\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{R}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{R},\gamma_{5}=\mathcal{T}\\}\;\\\
\end{matrix}\\!\right\\}\\!\\!$ (15)

$q_{15}^{R}$ and $\bar{q}_{15}^{R}$ are then equally strong, and their
construction provides a solution:

######  Solution 5.4.

A solution to the $5$ gods puzzle with 2 random and 3 truthful gods using
$4.15$ questions exists.

###### Proof.

Put $t_{q}(q_{1}^{5},\gamma_{1})$ to $\gamma_{1}$ and consider the possible
cases:

Case $t(q_{1}^{5},\gamma_{1})$:

Then $q_{15}^{R}$ (eq. (14)) holds by its construction, and theorem 2.2.

Given $q_{15}^{R}$, $\gamma_{2}$ is most likely to be non-random, and we’ll
ask her next.

We’ll again aim to split the remaining possibilities in two equally large
parts, and with gods likely to be non-random on both sides. Let

######  Definition 5.5.

$q_{2}^{5}\coloneqq$

$\bigvee\\!\\!\left\\{\\!\begin{matrix}\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{R}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{R},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{R},\gamma_{5}=\mathcal{R}\\}\;\vspace{0pt}\\\
\end{matrix}\\!\right\\}\\!\\!\\!\\!$ (16)

Then $\neg q_{2}^{5}\leftrightarrow$

$\bigvee\\!\\!\left\\{\\!\begin{matrix}\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{R}\\},\\\
\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{R},\gamma_{5}=\mathcal{T}\\}\;\\\
\end{matrix}\\!\right\\}\\!\\!\\!\\!\\!$ (17)

There is no more $\gamma_{2}=\mathcal{R}$ possibility to add to $q_{2}^{5}$,
but there is one for $\neg q_{2}^{5}$:

######  Definition 5.6.

$\bar{q}_{25}^{R}\coloneqq$

$\bigvee\\!\\!\left\\{\\!\begin{matrix}\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{R}\\},\\\
\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{R},\gamma_{5}=\mathcal{T}\\}\;\\\
\end{matrix}\\!\right\\}\\!\\!\\!\\!\\!\\!$ (18)

$q_{2}^{5}$ and $\neg q_{2}^{5}$ are balanced, and we’ll ask $\gamma_{2}$
about $q_{2}^{5}$ next.

Case $t(q_{2}^{5},\gamma_{2})$:

Then $q_{2}^{5}$ (eq. (16)) holds, by construction. Therefore
$\gamma_{3}\neq\mathcal{R}$ and is safe to ask.

Asking $\gamma_{3}$ about $\gamma_{4}\neq\mathcal{R}$ and
$\gamma_{5}\neq\mathcal{R}$ determine the rest of the gods.

This case used $4$ questions, and covered $4$ possibilities.

Case $\neg t(q_{2}^{5},\gamma_{2})$:

Then $\bar{q}_{25}^{R}$ (eq. (18)) holds, by construction.

Next we’ll go after $\gamma_{4}$, since it’s likely that she isn’t
$\mathcal{R}$.

We’ll again aim to split the remaining possibilities in two equally large
parts. Let

######  Definition 5.7.

$q_{3}^{5}\coloneqq$

$\bigvee\\!\\!\left\\{\\!\begin{matrix}\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{R}\\},\\\
\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{R},\gamma_{5}=\mathcal{T}\\}\;\\\
\end{matrix}\\!\right\\}\\!\\!\\!$ (19)

Then $\neg q_{3}^{5}\leftrightarrow$

$\bigvee\\!\\!\left\\{\\!\begin{matrix}\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\}\;\\\
\end{matrix}\\!\right\\}\\!\\!\\!$ (20)

There is no more $\gamma_{4}=\mathcal{R}$ possibility to add to $q_{3}^{5}$,
but there is one for $\neg q_{3}^{5}$:

######  Definition 5.8.

$\bar{q}_{35}^{R}\coloneqq$

$\bigvee\\!\\!\left\\{\\!\begin{matrix}\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{R},\gamma_{5}=\mathcal{T}\\}\;\\\
\end{matrix}\\!\right\\}\\!\\!\\!$ (21)

$q_{3}^{5}$ and $\neg q_{3}^{5}$ are as balanced as possible, and we’ll ask
$\gamma_{4}$ about $q_{3}^{5}$ next.

Case $t(q_{3}^{5},\gamma_{4})$:

Then $q_{3}^{5}$ (eq. (19)) holds, by construction. Therefore
$\gamma_{2}\neq\mathcal{R}$ and is safe to ask.

Asking $\gamma_{2}$ about $\gamma_{4}\neq\mathcal{R}$ determines the rest of
the gods.

This case used $4$ questions, and covered $2$ possibilities.

Case $\neg t(q_{3}^{5},\gamma_{3})$:

Then $\bar{q}_{35}^{R}$ (eq. (21)) holds, by construction. Therefore
$\gamma_{5}\neq\mathcal{R}$ and is safe to ask.

Asking $\gamma_{5}$ about $\gamma_{4}\neq\mathcal{R}$, and if needed asking
$\gamma_{5}$ about $\gamma_{3}\neq\mathcal{R}$, determine the rest of the
gods.

This case used $5$ questions for $2$ possibilities, and $4$ questions for $1$
possibility.

Case $\neg t(q_{1}^{5},\gamma_{1})$:

Then $\bar{q}_{15}^{R}$ (eq. (15)) holds, by construction.

We’ll go after $\gamma_{3}$ next. Let

######  Definition 5.9.

$q_{2}^{\bar{5}}\coloneqq$

$\bigvee\\!\\!\left\\{\\!\begin{matrix}\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{R}\\},\\\
\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{R}\\}\;\\\
\end{matrix}\\!\right\\}\\!\\!\\!\\!$ (22)

Then $\neg q_{2}^{\bar{5}}\leftrightarrow$

$\bigvee\\!\\!\left\\{\\!\begin{matrix}\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{R},\gamma_{5}=\mathcal{T}\\},\vspace{0pt}\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{R},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\}\;\\\
\end{matrix}\\!\right\\}\\!\\!\\!\\!\\!$ (23)

Adding $\gamma_{3}=\mathcal{R}$ possibilities to $q_{2}^{\bar{5}}$ and $\neg
q_{2}^{\bar{5}}$ gives

######  Definition 5.10.

$q_{2{\bar{5}}}^{R}\coloneqq$

$\bigvee\\!\\!\left\\{\\!\begin{matrix}\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{R}\\},\\\
\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{R}\\}\;\\\
\end{matrix}\\!\right\\}\\!\\!\\!\\!\\!\\!$ (24)

######  Definition 5.11.

$\bar{q}_{2{\bar{5}}}^{R}\coloneqq$

$\bigvee\\!\\!\left\\{\\!\begin{matrix}\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{R},\gamma_{5}=\mathcal{T}\\},\vspace{0pt}\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{R},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{T},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{R},\gamma_{2}=\mathcal{T},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\},\\\
\land\\{\gamma_{1}=\mathcal{T},\gamma_{2}=\mathcal{R},\gamma_{3}=\mathcal{R},\gamma_{4}=\mathcal{T},\gamma_{5}=\mathcal{T}\\}\;\\\
\end{matrix}\\!\right\\}\\!\\!\\!\\!\\!\\!$ (25)

$q_{2}^{\bar{5}}$ and $\neg q_{2}^{\bar{5}}$ are balanced, and we’ll ask
$\gamma_{3}$ about $q_{2}^{\bar{5}}$ next.

Case $t(q_{2}^{\bar{5}},\gamma_{2})$:

Then $q_{2{\bar{5}}}^{R}$ (eq. (24)) holds, by construction. Therefore
$\gamma_{4}\neq\mathcal{R}$ and is safe to ask.

Asking $\gamma_{4}$ about $\gamma_{2}\neq\mathcal{R}$ and
$\gamma_{3}\neq\mathcal{R}$ determine the rest of the gods.

This case used $4$ questions, and covered $4$ possibilities.

Case $\neg t(q_{2}^{\bar{5}},\gamma_{2})$:

Then $\bar{q}_{2{\bar{5}}}^{R}$ (eq. (25)) holds, by construction. Therefore
$\gamma_{5}\neq\mathcal{R}$ and is safe to ask.

Ask $\gamma_{5}$ about $\gamma_{4}\neq\mathcal{R}$:

If $\gamma_{4}\neq\mathcal{R}$,

then asking $\gamma_{5}$ about $\gamma_{1}\neq\mathcal{R}$, and if needed
asking $\gamma_{5}$ about $\gamma_{3}\neq\mathcal{R}$, determine all the gods.

This case used $5$ questions for $2$ possibilities, and $4$ questions for $1$
possibility.

If $\gamma_{4}=\mathcal{R}$,

then asking $\gamma_{5}$ about $\gamma_{1}\neq\mathcal{R}$ determines all
gods.

This case used $4$ questions, and covered $2$ possibilities.

∎

### 5.1 Average number of questions used

The number of questions used for each possibility is shown below (eq. (26)).
Some possibilites can be detected in more than one way. When that can happen,
and when the number of questions differ, the probability for each question
sequence is listed as well. As can be seen, it’s slightly better to try to
hide cases that can take $5$ questions among possibilites that have multiple
ways to get detected (e.g.,
$(\frac{1}{4}4+\frac{1}{4}5+\frac{1}{2}5)+4<\frac{4+5}{2}+\frac{4+5}{2}$).

$\begin{matrix}P\,|Qs|&\gamma_{1}&\gamma_{2}&\gamma_{3}&\gamma_{4}&\gamma_{5}\\\
\frac{1}{4}4,\frac{1}{4}5,\frac{1}{2}5&\mathcal{R}&\mathcal{R}&\mathcal{T}&\mathcal{T}&\mathcal{T}\\\
4,4&\mathcal{R}&\mathcal{T}&\mathcal{T}&\mathcal{T}&\mathcal{R}\\\
4,4&\mathcal{R}&\mathcal{T}&\mathcal{T}&\mathcal{R}&\mathcal{T}\\\
4&\mathcal{T}&\mathcal{T}&\mathcal{T}&\mathcal{R}&\mathcal{R}\\\
4&\mathcal{T}&\mathcal{T}&\mathcal{R}&\mathcal{T}&\mathcal{R}\\\
4,4&\mathcal{T}&\mathcal{T}&\mathcal{R}&\mathcal{R}&\mathcal{T}\\\
\frac{1}{2}5,\frac{1}{4}4,\frac{1}{4}5&\mathcal{R}&\mathcal{T}&\mathcal{R}&\mathcal{T}&\mathcal{T}\\\
4&\mathcal{T}&\mathcal{R}&\mathcal{T}&\mathcal{T}&\mathcal{R}\\\
4,4&\mathcal{T}&\mathcal{R}&\mathcal{R}&\mathcal{T}&\mathcal{T}\\\
4&\mathcal{T}&\mathcal{R}&\mathcal{T}&\mathcal{R}&\mathcal{T}\\\ \end{matrix}$
(26)

Thus, the average number of questions used to find a solution is
$(2(\frac{1}{4}4+\frac{1}{4}5+\frac{1}{2}5)+8\cdot 4)\;\div\;10\;=\;4.15$.

## 6 A top-down solution to the puzzle

######  Solution 6.1 (Tim Roberts’s solution).

Here is a solution to “The Hardest Logic Puzzle Ever” that is similar to Tim
Roberts’s solution.[3]

###### Proof.

We’ll start by asking $\gamma_{1}$ the question
$t_{q}(\gamma_{3}=\mathcal{R},\gamma_{1})$. Consider the possible cases:

Case $t(\gamma_{3}=\mathcal{R},\gamma_{1})$:

If $\gamma_{1}\neq\mathcal{R}$, then $\gamma_{3}=\mathcal{R}$ by theorem 2.2,
and $\gamma_{2}\neq\mathcal{R}$. If $\gamma_{1}=\mathcal{R}$, then
$\gamma_{2}\neq\mathcal{R}$ again. Hence we now know that
$\gamma_{2}\neq\mathcal{R}$ and is safe to question.

Next we’ll ask $\gamma_{2}$ about $\gamma_{1}\neq\mathcal{R}$ (because there
are $4$ possibilities left, half of which have $\gamma_{1}=\mathcal{R}$).

If $t(\gamma_{1}\neq\mathcal{R},\gamma_{2})$, then $\gamma_{3}=\mathcal{R}$,
and e.g. $t(\gamma_{2}=\mathcal{T},\gamma_{2})$ determines which is which of
$\gamma_{1}$ and $\gamma_{2}$.

If $\neg t(\gamma_{1}\neq\mathcal{R},\gamma_{2})$, then
$\gamma_{1}=\mathcal{R}$, and $t(\gamma_{2}=\mathcal{T},\gamma_{2})$
determines which is which of $\gamma_{2}$ and $\gamma_{3}$.

Case $\neg t(\gamma_{3}=\mathcal{R},\gamma_{1})$:

If $\gamma_{1}\neq\mathcal{R}$, then $\gamma_{3}\neq\mathcal{R}$ by theorem
2.2. If $\gamma_{1}=\mathcal{R}$, then $\gamma_{3}\neq\mathcal{R}$ again.
Hence $\gamma_{3}\neq\mathcal{R}$ and is safe to question.

Next we’ll ask $\gamma_{3}$ about $\gamma_{1}\neq\mathcal{R}$.

If $t(\gamma_{1}\neq\mathcal{R},\gamma_{3})$, then $\gamma_{2}=\mathcal{R}$,
and e.g. $t(\gamma_{3}=\mathcal{T},\gamma_{3})$ determines which is which of
$\gamma_{1}$ and $\gamma_{3}$.

If $\neg t(\gamma_{1}\neq\mathcal{R},\gamma_{3})$, then
$\gamma_{1}=\mathcal{R}$, and $t(\gamma_{3}=\mathcal{T},\gamma_{3})$
determines which is which of $\gamma_{2}$ and $\gamma_{3}$.

∎

## 7 A note on mathematical vs. computational thinking

Donald Knuth has distinguished beetween mathematical and computational
thinking.[5]

Gödel’s incompleteness theorems provide a particular type of mathematical
thinking. Their proofs consist of straightforward computational reasoning,
except for the fixed-point theorem, which requires a certain mathematical
thinking. Similarly, the foundation of computability is straightforward
computational, except for its fixed-point result, Kleene’s recursion theorem,
which is quite mathematical.[6, 7, 8, 9, 10]

In this article, while the rest is mostly straightforward computational
reasoning, the meta-question template, def. 2.3, is more of the mathematical
kind, perhaps.

## 8 Infinite number of gods

The results in section 4 about when a puzzle is solvable hold also when the
number of gods is infinite.

Let $\nu$ be the number of gods. Regard $\nu$ as an ordinal and let the gods
be $\Gamma\\!\coloneqq\bigcup_{\alpha<\nu}\\{\gamma_{\alpha}\\}$.

### 8.1 Finding a non-random god

For finding which type each god is, we’ll define a function $\bar{\varrho}$
that takes a well-ordered set of gods and returns a non-random god, if there
are more non-random than random gods.

Let $\bar{\varrho}(\\{\gamma\\})\coloneqq\gamma$. Let
$\bar{\varrho}(\\{\gamma,\\_\\})\coloneqq\gamma$, with $\gamma$ least, say.

For the successor case, we’ll ask the last god, $\gamma^{\prime}$. Go through
the gods, from least to greatest, until a random god
$\gamma_{\mathcal{\scriptscriptstyle R}}$ is found, i.e. until
$t(\gamma_{\mathcal{\scriptscriptstyle R}}=\mathcal{R},\gamma^{\prime})$, or
the search has reached the last god in which case we’ll set
$\gamma_{\mathcal{\scriptscriptstyle R}}$ to the least god. Then remove the
last god, $\gamma^{\prime}$; replace $\gamma_{\mathcal{\scriptscriptstyle R}}$
with the least god; and update the well-ordering accordingly, by removing the
last god, and handling the $\gamma_{\mathcal{\scriptscriptstyle R}}$
replacement.

Then we can recursively apply $\bar{\varrho}$ to the new set of gods and the
updated well-ordering; the result of this recursive application will be the
result of the successor case too.

For the limit case, the result of $\bar{\varrho}$ is the limit of
$\bar{\varrho}$ on the smaller sets. The limit exists if the non-random gods
are more than the random gods.

######  Lemma 8.1.

If a $\nu$ gods puzzle has strictly more non-random gods than random gods,
then it is solvable.

###### Proof.

Assume more non-random gods than random gods. Then we can use $\bar{\varrho}$
to find a non-random god $\gamma$. After that we can go through all the gods
and ask $\gamma$ about their type. ∎

### 8.2 Finding an unsolvable puzzle

Let $\mathscr{P}(\nu)$ be the set of all subsets of ordinals less than $\nu$.

######  Theorem 8.2.

A $\nu$ gods puzzle is solvable if and only if the number of random gods is
stricly less than the number of non-random gods.

###### Proof.

The $\Leftarrow$ case is covered by lemma 8.1.

For the $\Rightarrow$ case, consider the easiest to solve of such problems:
Assume that the random gods equal the non-random gods, and that there are only
truthful non-random gods.

$p_{n}$ (def. 4.5) from section 4 becomes

######  Definition 8.3.

$P_{\nu}\coloneqq$

$\bigcup_{\underset{|\alpha|<\aleph_{0}}{\alpha\in\mathscr{P}(\nu),}}\\{\,\bigvee\left\\{\begin{matrix}\bigwedge\limits_{\beta\in\alpha}\left\\{\begin{cases}\gamma_{\beta}\\!=\\!\mathcal{T},&\text{if
}\beta\text{ is even}\\\ \gamma_{\beta}\\!=\\!\mathcal{R},&\text{if
}\beta\text{ is odd}\end{cases}\right\\}\\!\\!,\\\
\bigwedge\limits_{\beta\in\alpha}\left\\{\begin{cases}\gamma_{\beta}\\!=\\!\mathcal{R},&\text{if
}\beta\text{ is even}\\\ \gamma_{\beta}\\!=\\!\mathcal{T},&\text{if
}\beta\text{ is odd}\end{cases}\right\\}\end{matrix}\right\\}\\}$ (27)

Let $P_{\mathcal{\scriptscriptstyle T}\mathcal{\scriptscriptstyle R}}$ and
$P_{\mathcal{\scriptscriptstyle R}\mathcal{\scriptscriptstyle T}}$ be the
conjunctions of $P_{\nu}$, similar to section 4.

######  Definition 8.4.

$P_{\mathcal{\scriptscriptstyle T}\mathcal{\scriptscriptstyle R}}\coloneqq$

$\bigcup_{\underset{|\alpha|<\aleph_{0}}{\alpha\in\mathscr{P}(\nu),}}\\{\bigwedge\limits_{\beta\in\alpha}\left\\{\begin{cases}\gamma_{\beta}\\!=\\!\mathcal{T},&\text{if
}\beta\text{ is even}\\\ \gamma_{\beta}\\!=\\!\mathcal{R},&\text{if
}\beta\text{ is odd}\end{cases}\right\\}\\}$ (28)

######  Definition 8.5.

$P_{\mathcal{\scriptscriptstyle R}\mathcal{\scriptscriptstyle T}}\coloneqq$

$\bigcup_{\underset{|\alpha|<\aleph_{0}}{\alpha\in\mathscr{P}(\nu),}}\\{\bigwedge\limits_{\beta\in\alpha}\left\\{\begin{cases}\gamma_{\beta}\\!=\\!\mathcal{R},&\text{if
}\beta\text{ is even}\\\ \gamma_{\beta}\\!=\\!\mathcal{T},&\text{if
}\beta\text{ is odd}\end{cases}\right\\}\\}$ (29)

Let $P_{\mathcal{\scriptscriptstyle T}\mathcal{\scriptscriptstyle R}}^{\nu}$
and $P_{\mathcal{\scriptscriptstyle R}\mathcal{\scriptscriptstyle T}}^{\nu}$
be the full descriptions of the puzzle instances:

######  Definition 8.6.

$P_{\mathcal{\scriptscriptstyle T}\mathcal{\scriptscriptstyle
R}}^{\nu}\coloneqq$

$\bigcup_{\beta<\nu}\left\\{\begin{cases}\gamma_{\beta}\\!=\\!\mathcal{T},&\text{if
}\beta\text{ is even}\\\ \gamma_{\beta}\\!=\\!\mathcal{R},&\text{if
}\beta\text{ is odd}\end{cases}\right\\}$ (30)

######  Definition 8.7.

$P_{\mathcal{\scriptscriptstyle R}\mathcal{\scriptscriptstyle
T}}^{\nu}\coloneqq$

$\bigcup_{\beta<\nu}\left\\{\begin{cases}\gamma_{\beta}\\!=\\!\mathcal{R},&\text{if
}\beta\text{ is even}\\\ \gamma_{\beta}\\!=\\!\mathcal{T},&\text{if
}\beta\text{ is odd}\end{cases}\right\\}$ (31)

Assume that the gods are as described by $P_{\mathcal{\scriptscriptstyle
T}\mathcal{\scriptscriptstyle R}}^{\nu}$ or $P_{\mathcal{\scriptscriptstyle
R}\mathcal{\scriptscriptstyle T}}^{\nu}$, and that hence $P_{\nu}$ holds.

If both $q$ and $\neg q$ are consistent with $P_{\nu}$, assume that the random
gods always happen to give the incorrect answer to a question about $q$. If
only one of $q$ and $\neg q$ is consistent with $P_{\nu}$, assume that the
random gods always happen to give the correct answer to a question about $q$.

We should be able to conclude that $P_{\nu}$ (eq. (27)) holds, if we reason in
e.g. set theory. Because we can ask more gods than there are random gods about
$P_{\nu}$. Since everyone will answer that $P_{\nu}$ holds we can conclude
that since we have asked at least one truthful god, $P_{\nu}$ must hold.

Next we’ll show that if $P_{\nu}\\!\nvdash q$ and $P_{\nu}\\!\nvdash\neg q$,
then $P_{\nu}\\!\vdash q\\!\leftrightarrow\\!\phi_{\mathcal{\scriptscriptstyle
T}\mathcal{\scriptscriptstyle R}}$ for all $\phi_{\mathcal{\scriptscriptstyle
T}\mathcal{\scriptscriptstyle R}}\\!\in\\!P_{\mathcal{\scriptscriptstyle
T}\mathcal{\scriptscriptstyle R}}$, or $P_{\nu}\\!\vdash
q\leftrightarrow\phi_{\mathcal{\scriptscriptstyle
R}\mathcal{\scriptscriptstyle T}}$ for all $\phi_{\mathcal{\scriptscriptstyle
R}\mathcal{\scriptscriptstyle T}}\\!\in\\!P_{\mathcal{\scriptscriptstyle
R}\mathcal{\scriptscriptstyle T}}$.

Assume $P_{\nu}$, $P_{\nu}\\!\nvdash q$ and $P_{\nu}\\!\nvdash\neg q$. Then
$q$ has a model $\mathcal{M}$ (i.e. an assignment of the gods) where $q$, and
$P_{\nu}$, are true. Suppose, without loss of generality, that it’s
$P_{\mathcal{\scriptscriptstyle T}\mathcal{\scriptscriptstyle R}}$ that’s true
in $\mathcal{M}$. Then, since $P_{\mathcal{\scriptscriptstyle
T}\mathcal{\scriptscriptstyle R}}$ completely determines a model, $q$ holds
whenever $P_{\mathcal{\scriptscriptstyle T}\mathcal{\scriptscriptstyle R}}$
does, i.e. $\phi_{\mathcal{\scriptscriptstyle T}\mathcal{\scriptscriptstyle
R}}\\!\rightarrow\\!q$ for $\phi_{\mathcal{\scriptscriptstyle
T}\mathcal{\scriptscriptstyle R}}\\!\in\\!P_{\mathcal{\scriptscriptstyle
T}\mathcal{\scriptscriptstyle R}}$. Suppose
$\neg\phi_{\mathcal{\scriptscriptstyle T}\mathcal{\scriptscriptstyle R}}$ for
$\phi_{\mathcal{\scriptscriptstyle T}\mathcal{\scriptscriptstyle
R}}\\!\in\\!P_{\mathcal{\scriptscriptstyle T}\mathcal{\scriptscriptstyle R}}$.
Then $P_{\mathcal{\scriptscriptstyle R}\mathcal{\scriptscriptstyle T}}$. Since
$P_{\mathcal{\scriptscriptstyle R}\mathcal{\scriptscriptstyle T}}$ determines
its models completely, if $q$ where to hold, then $q$ would hold in all models
to $P_{\nu}$, contradicting $P_{\nu}\\!\nvdash q$. Hence $\neg q$ holds, i.e.
$\neg\phi_{\mathcal{\scriptscriptstyle T}\mathcal{\scriptscriptstyle
R}}\\!\rightarrow\\!\neg q$.

Assume $P_{\nu}$ (eq. (27)). To see that if $P_{\nu}$ is known, no more
conclusions can be made, suppose that $\gamma_{\alpha}\\!=\\!\mathcal{T}$,
with $\alpha$ even say. Suppose $\gamma_{\alpha}$ is asked about $q$. Suppose
$P_{\nu}\\!\nvdash q$ and $P_{\nu}\\!\nvdash\neg q$. Then an answer that $q$
(or $\neg q$) holds (with implications that $\phi_{\mathcal{\scriptscriptstyle
T}\mathcal{\scriptscriptstyle R}}$ holds, for
$\phi_{\mathcal{\scriptscriptstyle T}\mathcal{\scriptscriptstyle
R}}\\!\in\\!P_{\mathcal{\scriptscriptstyle T}\mathcal{\scriptscriptstyle R}}$)
is undone because we can only conclude that
$q\vee\gamma_{\alpha}\\!=\\!\mathcal{R}$ (or $\neg
q\vee\gamma_{\alpha}\\!=\\!\mathcal{R}$), which is equivalent to formulas in
$P_{\nu}$.

Similarly, if instead $\gamma_{\alpha}=\mathcal{R}$, then we are able to
conclude only $q\vee\gamma_{\alpha}\\!=\\!\mathcal{R}$ (or $\neg
q\vee\gamma_{\alpha}\\!=\\!\mathcal{R}$). If both $q$ and $\neg q$ are
consistent with $P_{\nu}$, the false answer that $q$ (or $\neg q$) holds
undoes the disjunct $\gamma_{\alpha}=\mathcal{R}$.

If $q$ is already known, the concluded disjunction,
$q\vee\gamma_{1}\\!=\\!\mathcal{R}$ (or $\neg
q\vee\gamma_{1}\\!=\\!\mathcal{R}$), will already be known too, and nothing
new can be concluded again. ∎

## References

  * Boolos [1996] George Boolos.  The hardest logic puzzle ever.  _The Harvard Review of Philosophy_ , 6:62–65, Spring 1996\.  https://doi.org/10.5840/harvardreview1996615.
  * Gendler [2017] Alex Gendler.  Can you solve the three gods riddle?, 2017.  https://www.youtube.com/watch?v=LKvjIsyYng8.
  * Roberts [2001] Tim S. Roberts.  Some thoughts about the hardest logic puzzle ever.  _Journal of Philosophical Logic_ , 30(6):609–612, 2001.  https://www.researchgate.net/publication/227024817_Some_Thoughts_about_the_Hardest_Logic_Puzzle_Ever.
  * Rabern and Rabern [2008] Brian Rabern and Landon Rabern.  A simple solution to the hardest logic puzzle ever.  _Analysis_ , 68(2):105–112, April 2008.  https://www.pure.ed.ac.uk/ws/files/15023904/Simple_Solution.pdf.
  * Albers and Alexanderson [2008] Donald Albers and Gerald L. Alexanderson.  _Mathematical People: Profiles and Interviews_ , chapter Donald Knuth, pages 190–195.  A K Peters/CRC Press, 2008.
  * Franklin and Quader [2013] Johanna Franklin and Saad Quader.  Kleene’s Recursion Theorem: A Proof for Beginners, 2013.  https://saadquader.wordpress.com/2013/02/07/kleenes-recursion-theorem/.
  * Jr. [1973] James C. Owings Jr.  Diagonalization and the recursion theorem.  _Notre Dame Journal of Formal Logic_ , 14(1):95 – 99, 1973.  http://logic.amu.edu.pl/images/b/b1/Jamesowings.pdf.
  * Jr. [1989] James C. Owings Jr.  Corrigendum to “Diagonalization and the recursion theorem”.  _Notre Dame J. Formal Log._ , 30(1):153, 1989\.  https://projecteuclid.org/journals/notre-dame-journal-of-formal-logic/volume-30/issue-1/Corrigendum-to-Diagonalization-and-the-recursion-theorem/ndjfl/1093635004.full.
  * [9] Linda Brown Westrick.  Arithmetic fixed point theorem.  MathOverflow.  https://mathoverflow.net/q/31374.
  * [10] Joel David Hamkins.  Arithmetic fixed point theorem.  MathOverflow.  https://mathoverflow.net/q/31649.