[Part 6] Raymond Smullyan's Certified Knights and Knaves puzzles Puzzle #6 - Analysis

For our sixth puzzle, we will solve Problem 6 on page 42 of the 2013 Dover edition [ISBN: 978-0486497051] of Raymond Smullyan's 2013 book entitled "The Gödelian Puzzle Book - Puzzles, Paradoxes & Proofs", which reads:

On another particularly interesting occasion I came across two natives A and B each of whom made a statement such that I could infer that at least one of them must be an uncertified knight, but there was no way to tell which one it was. From neither statement alone could one have deduced this.

What two statements would work? [This problem is not easy!]

One reason this puzzle is tricky is because it involves two natives and requires us to "go backwards" from the inferred fact back to the statements.

Another reason why it is not easy is that the inferred fact is a bit hard to interpret. 

When Smullyan writes:

"at least one of them must be an uncertified knight, but there was no way to tell which one it was."

the initial adverbial phrase "at least" implies that we need to consider three possibilities:

1. Only A is an uncertified knight.
2. Only B is an uncertified knight.
3. Both A and B are uncertified knights.

However, if exactly one of these possibilities is the case, then there IS a way to tell which native is a certified knight.

Therefore, the second half of the inferred fact above (namely, "but there was no way to tell...") implies that more than one of these possibilities must be SIMULTANEOUSLY compatible with the two statements made by the native.

The possible combinations of these possibilities are (shown as sets):

• {1,2}
• {1,3}
• {2,3}
• {1,2,3}

But are all combinations compatible with the puzzle statement?

This is where the puzzle may be open to several interpretations.

In my interpretation, the first and last bullet points are compatible with the puzzle statement:

• With {1,2}, exactly one of the two natives is an uncertified knight but there is no way to tell which one.
• With {1,2,3}, either one or both of the natives could be an uncertified knight but there is no way to tell whether A is an uncertified knight nor whether B is an uncertified knight.

In contrast (again, in my interpretation), the second and third bullet points above are NOT compatible with the puzzle statement:

• With {1,3}, B may or may not be an uncertified knight but it is certain that A is one.
• With {2,3}, A may or may not be an uncertified knight but it is certain that B is one.

To me, knowing for sure that one of the natives is an uncertified knight contradicts the requirement that "there was no way to tell which one it was."

Therefore, in my analysis of the puzzle, the two statements made by the natives allow us to infer that:

• either: exactly one of A and B is an uncertified knight, but there is no way to tell which one is
• or: at least one of A and B is an uncertified knight, but there is no way to tell which one is or if both are

This analysis led me to reason as follows.

First, since this problem involves two natives, we will again use the proposition \(A\) (respectively, \(B\)) to represent the fact that A (respectively, B) is a knight. And we will use the proposition \(Ac\) (respectively, \(Bc\)) to represent the fact that A (respectively, B) is certified.

Second, we are looking for two statements \(S_A\) and \(S_B\), encoded as formulas \(\varphi_A\) and \(\varphi_B\), respectively, such that the formula:

\(\varphi = (A \leftrightarrow \varphi_A)\ \&\ (B \leftrightarrow \varphi_B)\)

represents the puzzle correctly.

Third, the formulas \(\varphi_A\) and \(\varphi_B\) must satisfy the requirements represented by the following truth table:

\(A\)	\(Ac\)	\(B\)	\(Bc\)	\(\varphi = (A \leftrightarrow \varphi_A)\ \&\ (B \leftrightarrow \varphi_B)\)
\(F\)	\(F\)	\(F\)	\(F\)	\(F\)
\(F\)	\(F\)	\(F\)	\(T\)	\(F\)
\(F\)	\(F\)	\(T\)	\(F\)	\(T\)	only B
\(F\)	\(F\)	\(T\)	\(T\)	\(F\)
\(F\)	\(T\)	\(F\)	\(F\)	\(F\)
\(F\)	\(T\)	\(F\)	\(T\)	\(F\)
\(F\)	\(T\)	\(T\)	\(F\)	\(T\)	only B
\(F\)	\(T\)	\(T\)	\(T\)	\(F\)
\(T\)	\(F\)	\(F\)	\(F\)	\(T\)	only A
\(T\)	\(F\)	\(F\)	\(T\)	\(T\)	only A
\(T\)	\(F\)	\(T\)	\(F\)	\(T\)	both A and B
\(T\)	\(F\)	\(T\)	\(T\)	\(T\)	only A
\(T\)	\(T\)	\(F\)	\(F\)	\(F\)
\(T\)	\(T\)	\(F\)	\(T\)	\(F\)
\(T\)	\(T\)	\(T\)	\(F\)	\(T\)	only B
\(T\)	\(T\)	\(T\)	\(T\)	\(F\)

In the table above:

• the green rows correspond to the possibility "Only A is an uncertified knight",
• the red rows correspond to the possibility "Only B is an uncertified knight", and 
• the blue row corresponds to the possibility "Both A and B are uncertified knights".

In the next few posts, we'll describe a JavaScript program that will find an answer to this puzzle, that is, formulas \(\varphi_A\) and \(\varphi_B\) such that the formula \(\varphi\) is:

• always False in the white rows
  AND
  • EITHER [case {1,2}]:
    • True in one or more green rows
      AND
    • True in one or more red rows
  • OR [case {1,2,3}]:
    • True in one or more green rows
      AND
    • True in one or more red rows
      AND
    • True in the blue row

Phew!

Now you see why I split my discussion of this puzzle into several posts:

1. this post to specify my interpretation of the puzzle and pin down its requirements, and
2. the next posts describing how I solved the puzzle (according to this interpretation) using a JavaScript program.

Before moving on to the code though, we make the following observation.

Since the requirements in the {1,2} case are a strict subset of the requirements in the {1,2,3} case, the extra requirement (numbered 3) is really optional.  In other words, we simply need to find statements that meet the requirements of case {1,2}.

So, as a simplification, we will be looking for formulas \(\varphi_A\) and \(\varphi_B\) such that the formula \(\varphi\) is:

• always False in the white rows
  AND
• True in one or more green rows 
  AND
• True in one or more red rows