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).


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.


Thursday, May 9, 2019

star polygon fun

Star and compound polygons are pretty mathematical objects that are fun to draw or create in code.
star and compound polygons
on 2 to 9 vertices

You might draw ten pointed polygons while exploring the multiplication table, for example. In the picture below, skip counting by 6 while drawing a line between the last digits of consecutive numbers gives us a pentagon: counting 0, 6, 12, 18, 24, 30 we draw lines connecting 0, 6, 2, 8, 4, and 0.

skip counting by 6 draws {5/2}

When drawing star and compound polygons by hand, you start with n points spaced evenly around a circle, and then from each point connect to another, always skipping over the same number of points. If you skip over 0 points, you get the regular n-gon. If you skip over k points, and k+1 is relatively prime with n, you will get a star polygon, if n and k+1 share factors, you get a compound of several regular or star polygons.

On 9 points, skipping over 0, 1, 2, and 3
vertices

It is interesting how an easy to describe algorithm like this, skipping around points on a circle, translates into a program.

The polygons on this page are drawn using some JavaScript (code here), which includes some use of trig functions to place the initial vertices (like points around a unit circle) and modular arithmetic to help traverse the list of points in a circular way. It's a nice example of how math makes its way into how we implement even simple algorithms.

When we go fully over to a mathematical way of expressing how to draw these by using desmos, we can see how mathematics can, in this case, express the algorithm in a surprisingly compact way. You can check out the graph here.

desmos sketch of {7/2},
graph here


Related links and posts
star polygon page
star polygons in desmos
polygons in the multiplication table

Wednesday, May 8, 2019

Desmos Chladni

Like Lissajous figures, Chladni figures provide a surprising and aesthetically engaging example of wave interaction.

Named for Ernst Chladni, these figures represent nodal patterns formed by vibrating surfaces. Traditionally, these are formed placing fine particles on a surface, like a sheet of metal that is set vibrating (a violin bow against an edge of the metal plate is one popular method). The particles settle in the areas of the surface that have the least motion - the nodes. When you achieve a resonant frequency, a characteristic pattern emerges.

In past posts I've pointed to code that draws Chladni figures using R (here and here), and using JavaScript. Maybe not surprisingly, you can also play around with Chladni-like figures using Desmos, and this may be the most accessible way to explore them them and appreciate how they are generated from the sinusoidal functions.

Chladni-like figure generated in R

Chladni-like figure generated using JavaScript


In Desmos, you can create images similar to these using inequalities. The equations are reasonably straight forward - the graph here will draw the figure across the whole plane - best results are seen when zooming in on a small region.

Chladni-like figure generated in Desmos,
graph here


More Chladni-like figures in Desmos

Try playing around with the desmos graph here, R scripts for generating figures are found here, the JavaScript Chladni generating page is here.

Update
After posting on Twitter, the desmos sketches were improved by   and @PaulaKrieg. Here are some other graphs inspired by their changes:

A Chladni-like pattern with
two distinct inequalities

A Chladni-like pattern with three distinct
inequalities

With the added layers, the Chladni patterns are approaching an abstract William Morris appearance.

Another Update
This other graph allows you to experiment more directly with the Chladni figures, similar to the web page mentioned above.

graph for building 
Chladni figures