Tuesday, September 8, 2020

gods, demons, and mortals

Raymond Smullyan's To Mock a Mockingbird introduces an interesting variation on the classic knights and knaves logic puzzles. The lying knaves and truthful knights are joined by beings from another dimension: lying demons and truthful gods. 

Adding in new kinds of liars and truth-tellers initially increases the number of puzzles and provides interesting variations. However, without making other changes to the puzzle format, having more than two varieties of liars and truth-tellers diminishes the number of puzzles that can be generated and reduces the available puzzles to essentially two uninteresting varieties.

The setup of the standard knights and knaves puzzle is that there is a region in which there are two kinds of inhabitants: knights who always tell the truth, and knaves who always lie. Knights and knaves are said to be on different "sides." We imagine that a traveller meets a group of these inhabitants and attempts to sort out what type they are based on some statements that the inhabitants make.

Let's see how introducing gods and demons changes a set of knights and knave puzzles. Consider puzzles where there are two inhabitants (Alice and Bob) who could be knights or knaves. A and B each make a statement from this list of 10 possible statements: (1) I am a liar, (2) I am a truth-teller, (3) They are a truth-teller, (4) They are liar, (5) At least one of us is a truth teller, (6) At least one of us is a liar, (7) We are liars, (8) We are truthful, (9) We are on the same side, (10) We are on different sides.

If we consider combinations of pairs of these statements, made by A and B respectively, some pairs will create a situation where there are no solutions (either A or B say "I am a liar") or many solutions (both A and B say "I am a truth teller"). Some will result in legitimate puzzles, where there is exactly one possible solution. The 38 puzzles we can generate from these are indicated in the chart below by a blue square in the chart below, where rows and columns that generate no puzzles (like "I am a liar") have been removed.

knights and knave puzzles from some simple statements

When there are only knights and knaves, some of these statements tell us quite a bit.

(1) An inhabitant says "I am a liar." This statement generates the famous liar paradox, and will not occur in any puzzle, as neither knights nor knaves can say this.

(2) An inhabitant says "I am truthful." This statement tells us nothing, so can only occur when the other statement tells us everything. Both knights and knaves can say this.

(3) An inhabitant says "They are a truth-teller." This tells us that the inhabitants are the same type, as a knave will say this of a knave, and a knight will say it of a knight.

(4) An inhabitant says "They are a liar." This tells us that the inhabitants are different types, as a knave will say this of a knight, and a knight will say it of a knave.

(5) An inhabitant says "At least one of us is a truth teller." This tells us that if the speaking inhabitant is a knave, then so is the other inhabitant.

(6) An inhabitant says "At least one of us is a liar." This tells us that the speaker cannot be a knave (if they were the statement would be true), so the speaker must be a knight and the other must be a knave.

(7) An inhabitant says "We are liars." The speaker cannot be a knight, so the speaker must be a knave and the other must be a knight (to ensure that the statement is not true).

(8) An inhabitant says "We are truthful." This tells us that if the speaking inhabitant is a knight, then so is the other inhabitant.

(9) An inhabitant says "We are on the same side." This tells us that the other inhabitant must be a knight (a knave would say this about a knight, and so would a knight).

(10) An inhabitant says "We are on different sides." This tells us that the other inhabitant must be a knave (a knave would say this about a knave, and so would a knight).

If we add gods and demons to these puzzles, no combinations of the statements as they are written will generate a proper single-solution puzzle. But we can change some statements to make them more productive. "I am a liar" can be replaced by its variation "I am a knave," which can actually be said by a demon without contradiction, or "I am not a knight," which can be stated by a god. One approach to generalizing a statement like "We are truthful" is to think of it as saying "I am a knight and they are a knight" and consider other pairs of "and" statements (like "I am a demon and they are a knave"). Similarly "At least one of us is a liar" is the same as "I am a knave or they are a knave" and can be extended to other "or" statements involving different types. With these additional statements, we can generate 204 puzzles involving gods, demons, knights, and knaves as shown in the chart below.


gods, demons, and mortals puzzles from some simple statements

What if we extend this further, and consider not only two types of liars or truth-tellers, but three? We could have three types of liars: knave-0, knave-1, and knave-2, and three types of truth-tellers: knight-0, knight-1, and knight-2. Still limiting the number of inhabitants in each possible puzzle to 2, this increases the number of statements significantly.

However, when we do this, our puzzles become supremely uninteresting. The only puzzles occur when one inhabitant makes a statement that ensures the other is telling the truth, while the second explicitly says what types both inhabitants are. There are only 54 puzzles from these statements, summarized in the chart below. As with the other charts, rows and columns with no puzzles at all have been removed. You can find a smaller copy of this uninteresting set of puzzles in the "gods and demons" chart shown above.


3 types of liars and 3 types of truth-tellers: this situation
allows for a very restricted set of puzzles

Introducing gods and demons, along with some additional statements, produces an interesting set of  "two inhabitant" puzzles, but increasing the number of different types of liars and truth-tellers beyond this causes the puzzle set to contract and become less varied. Perhaps there is a way of varying the statements or changing the puzzle format to make more general n-knight and n-knave puzzles richer?

A set of generated gods, demons, and mortals puzzles can be found here: https://dmackinnon1.github.io/godsAndDemons/

from barn quilts to mosque tilings

While travelling around southern Ontario recently, I enjoyed seeing barn quilts along the highway as we drove. Some barn quilts are truchet patterns; others, although not limited to using the truchet tile are based on a grid and can be created without a compass.

A truchet pattern that would make a
nice barn quilt

The truchet pattern above is an instance of a star pattern that often comes up in grid doodles - this "inner star" and the related "outer star" can be found, for example, in Froebelian gifts and guides (see The Kindergarten Guide by Maria Kraus-Boelté and John Kraus, 1877).


outer star and inner star (after fig 299 in
The Kindergarten Guide)


The "outer star" can be obtained from the "inner star" by inverting each of its indentations.

outer and inner
superimposed

If we extend all edges of the outer star, we get a new "greater star" that fills a 10x10 grid.

the greater star: an extension of
the outer star

Extending each edge of the great star a unit further and connecting the edges as shown below, we get a 12x12 florette pattern
greater star florette and tiling

Using this pattern as the unit of a tessellation, we get an approximation of a tiling found at the Kairouan Mosque (see here also).