liv. Knights and Knaves

Problem (Smullyan). On an island, knights always tell the truth and knaves always lie. From what the inhabitants say, deduce who is what.

Method. A statement $S$ made by $X$ means exactly $\text{knight}(X)⟺S$. Each puzzle is a boolean formula over the unknown types: try all $2^n$ assignments (or hand it to a SAT solver), and keep the consistent ones.

Puzzle	Solution
A: “We are both knaves.”	A knave, B knight
A: “At least one of us is a knave.”	A knight, B knave
A: “I am a knave.”	nobody can say it (no consistent assignment)
A: “I am a knight.”	no information (both assignments consistent)
A: “B is a knave.” B: “A and C are the same type.” What is C?	C is a knave
two doors, two guards (one always lies), one question	ask either: “Which door would the other guard say leads out?” and take the other door
a road fork, one islander of unknown type, one question	”If I asked you whether the left road leads to the village, would you say yes?“
three gods (Boolos): True, False and Random answer “ja”/“da”, meaning of “ja” unknown; three yes/no questions	below

Embedded question lemma. Let $E(Q)$ = “If I asked you $Q$, would you say ja?”. Both a truth-teller and a liar answer ja to $E(Q)$ iff $Q$ is true, whatever “ja” means.

Three gods solution.

1. Ask B: $E(\text{"Is A Random?"})$. If ja, C is not Random; if da, A is not Random. Call that god X.
2. Ask X: $E(\text{"Are you False?"})$: ja means X is False, da means X is True.
3. Ask X: $E(\text{"Is B Random?"})$: ja means B is Random, da means the god other than X and B is Random. The last god is the remaining type.

// Knights (bit 1) and knaves: each statement (speaker, claim) means knight(speaker) == claim(types).
vector<int> knightsAndKnaves(int n, const vector<pair<int, function<bool(int)>>>& st) {
    vector<int> res;
    for (int m = 0; m < (1 << n); m++) {
        bool ok = true;
        for (auto& [s, f] : st) if (bool(m >> s & 1) != f(m)) { ok = false; break; }
        if (ok) res.push_back(m);
    }
    return res;
}
 
// Three gods. type: 0 True, 1 False, 2 Random; jaYes: "ja" means yes. Returns true if the god says "ja".
bool says(int type, bool p, bool jaYes, bool rnd) {
    if (type == 2) return rnd;
    bool yes = type == 0 ? p : !p;
    return yes == jaYes;
}
bool embedded(int type, bool q, bool jaYes, bool rnd) {     // "If I asked you q, would you say ja?"
    if (type == 2) return rnd;
    return says(type, says(type, q, jaYes, false), jaYes, false);
}
array<int, 3> threeGods(const array<int, 3>& g, bool jaYes, int rndBits) {   // returns the deduced types of A, B, C
    int q = 0; auto ask = [&](int who, bool prop) { return embedded(g[who], prop, jaYes, rndBits >> q++ & 1); };
    int X = ask(1, g[0] == 2) ? 2 : 0;                        // a god who is surely not Random
    int tX = ask(X, g[X] == 1) ? 1 : 0;
    int R = ask(X, g[1] == 2) ? 1 : 3 - X - 1;               // the Random god
    array<int, 3> res; res[X] = tX; res[R] = 2; res[3 - X - R] = 1 - tX;
    return res;
}

Proof: the embedded question lemma and the three gods

Lemma. Write $j$ for “ja means yes”. A truth-teller says ja to a proposition $P$ iff $P⟺j$; a liar iff $\neg P⟺j$. For $E(Q)$ the proposition is $P=$ “I would say ja to $Q$”. Truth-teller: $P=(Q⟺j)$, so they say ja iff $(Q⟺j)⟺j$, i.e. iff $Q$. Liar: $P=(\neg Q⟺j)$, and they say ja iff $\neg P⟺j$; since $\neg (\neg Q⟺j)=(Q⟺j)$, this is $(Q⟺j)⟺j$, i.e. $Q$ again. The road question is the same lemma with “yes” for “ja”.

Gods. Step 1: if B is Random, the answer is meaningless, but then A and C are both not Random, so either conclusion is right. If B is not Random, by the lemma ja means A is Random (so C is not) and da means A is not Random. Either way X is not Random, so steps 2 and 3 get meaningful answers: by the lemma, step 2 answers “X is False”, step 3 answers “B is Random”; if not, Random is the god that is neither X nor B (X is not Random). The remaining god has the remaining type. threeGods checks this for all 6 arrangements, both meanings of ja, and every possible sequence of Random’s answers.

Two guards. If the door to freedom is $d$: asking the truth-teller, he truthfully reports the liar’s answer, which is the wrong door; asking the liar, he lies about the truth-teller’s answer $d$, again naming the wrong door. So the named door is always wrong.

Small puzzles. “We are both knaves”: if A were a knight, the statement would be false; so A is a knave and the statement is false, so not both are knaves: B is a knight. “At least one of us is a knave”: a knave saying it would make it true; so A is a knight and B a knave. “I am a knave”: true from a knight is impossible, and false from a knave means he is a knight. The three-person puzzle: if A is a knight, B is a knave, so A and C differ, C is a knave; if A is a knave, B is a knight, so A and C are the same: C is a knave. All verified with knightsAndKnaves.

Related notes

• Satisfiability
• Zebra Puzzle
• Blue-Eyed Islanders (another logic puzzle)