Tuesday, June 4, 2019

day-knights and night-knights

In his book To Mock a Mockingbird, Raymond Smullyan provides another variation on his classic 'knights and knave' puzzles, in which he imagines the puzzle solver not visiting an island, but exploring a bizarre underground city.


Illustration from The Child of the Cavern:
Or, Strange Doings Underground (sometimes published as
The Underground City) by Jules Vern

In the strange community of Subterranea, visitors cannot tell day from night, but the residents can. The residents are of two types: day-knights or night-knights. Day-knights tell the truth during the day and lie at night, while night-knights tell the truth at night and lie during the day.

Several Subterranea puzzles are presented in To Mock a Mockingbird, but we want more. If we consider a long enough list of statements that Subterraneans might make and  the possibilities presented if we have two inhabitants speaking, we should be able to generate quite a few puzzles.

Let's use these 22 statements:

0: I am a day-knight, and it is day
1: The other person is a day-knight, and it is day
2: I am a day-knight, and the other person is a day-knight
3: I am a day-knight, and it is night
4: The other person is a day-knight, and it is night
5: I am a night-knight, and the other person is a day-knight
6: I am a night-knight, and it is day
7: The other person is a night-knight, and it is day
8: I am a day-knight, and the other person is a night-knight
9: I am a night-knight, and it is night
10: The other person is a night-knight, and it is night
11: I am a night-knight, and the other person is a night-knight
12: It is day
13: I am a day-knight
14: It is not night
15: It is night
16: I am a night-knight
17: It is not day
18: At least one of us is a night-knight
19: At least one of us is a day-knight
20: We are both night-knights
21: We are both day-knights

Some of these are simple statements about the day or the type of one of the inhabitants, others are compound 'and' statements that combine two simple statements. When a compound statement uses "and" to join two simple statements, both simple statements need to be true in order for the compound statement to be true, but only one simple statement needs to be false in order for the compound statement to be false.

truth table for A and B

If the first inhabitant make statement 1, and the second inhabitant make statement 8, we get puzzle 5 (shown below). You can try to solve it here.


It turns out (not surprisingly, as we will see below) that both inhabitants are lying, at least somewhat.  It must be that it is night, and that both inhabitants are day-knights.

Here's one way to puzzle it out:

  • If the first person was telling the truth, there is one possibility: it is day, the first person is a day-knight, and the second person is a day-knight. There are 3 ways they could be lying.  If it is day, then they would have to be a night-knight, and the other person would also have to be a night-knight. If it is night, then they have to be a day-knight, and the other person could be either a day-knight or a night-knight.
  • If the second person is telling the truth, there is one possibility: it is night, the first person is a night-knight, and the second person is a night-knight. As with the first person, there are 3 ways the second person could be lying. If it is night, second person must be a day-knight, and the first person could either be a day-knight or night-knight. If it is day, then the second person must be a night-knight, and the first must be a day-knight.
  • The only option from both sets of possibilities is that it is night and that both inhabitants are day-knights.
In the set of 22 x 22 combinations of two statements how many lead to puzzles with unique solutions? It turns out that only 90 puzzles emerge - the graph below shows white squares for all combinations that lead to valid puzzles, black squares for those that do not.  It doesn't matter which inhabitant is making a particular statement, leading to the symmetry in the graph and duplication in the puzzles (if you don't care about statement order).

puzzles generated by the 22 statements

We can see that two statements in particular lead to almost complete horizontal and vertical lines of well-formed puzzles. These lines are puzzles that involve statements 3 and 6:

3: I am a day-knight, and it is night
6: I am a night-knight, and it is day
Each of these statements on its own narrows the field of possible solutions considerably. For example, if an islander says "I am a day-knight, and it is night," they must be lying. Moreover, we know that they cannot be a day-knight in the day, or a night-knight in the night. This leaves one possibility: that it is day and that they are a night-knight.

As expected from the symmetry of the statements, in the valid puzzles it is just as likely for it to be day as night, and it is just as likely for the inhabitants to be day-knights or night-knights.

day and night are equally likely

But not everything is balanced in Subterranea. In the example above (puzzle 5), and in puzzles generated by statements 3 and 6, we find the inhabitants of Subterranea being less than truthful. In fact, in all the puzzles generated, at least one of the inhabitants is lying - never do both tell the truth at the same time. The graph below shows puzzles where one inhabitant is lying in light blue, and where both inhabitants are lying in white.

Subterranea: not great for tourists

Perhaps it is their preference for AND conjunctions that leads the Subterraneans to have problems with telling the truth?

The Subterraneans might remind you of the inhabitants of the Isle of Dreams - a key difference between the Subterranean puzzles and the Isle of Dreams puzzles presented on this page is that the islanders do not link their statements using AND - each statement is distinct.

Both Subterranea and the Isle of Dreams are examples of a puzzle category that also includes standard Knights and Knaves, the Lion and the Unicorn, the Unreliable Guards, Tiger or TreasurePortia's Caskets, and many others. A bunch of these puzzles are collected here.