Thursday, May 17, 2018

The Isle of Dreams

After a short break, we are returning to some logic puzzles inspired by those of Raymond Smullyan. Earlier we visited the island of knights and knaves, looked into Portia's caskets, explored the case files of Inspector Leslie Craig, and looked behind doors for tigers and treasure. In this post, we are visiting the Isle of Dreams. As Smullyan says in his book The Lady or The Tiger?:
I once dreamed that there was a certain island called the Isle of Dreams. The inhabitants of this island dream quite vividly; indeed, their thoughts while asleep are as vivid as while awake. Moreover, their dream life has the same continuity from night to night as their waking life has from day to day. As a result, some of the inhabitants sometimes have difficulty in knowing whether they are awake or asleep at a given time.
Now, it so happens that each inhabitant is of one of two types: diurnal or nocturnal. A diurnal inhabitant is characterised by the fact that everything he believes while he is awake is true, and everything he believes while he is asleep is false. A nocturnal inhabitant is the opposite: everything a nocturnal person believes while asleep is true, and everything he believes while awake is false.
On this island then, each islander has a type (diurnal or nocturnal), and a state (awake or asleep), and based on their type and state, you can assess the veracity of their thoughts (either true or false).

To play around with this, I decided to make some puzzles similar to ones found in The Lady or The Tiger?, but based on the thoughts of two islanders A and B. Each islander has two distinct thoughts: one about themselves (either about their state or their type), and one about the other (either their state or their type). Importantly, these thoughts occur to both A and B at exactly the same time. Here is an example:

• Islander A has two distinct thoughts at the same moment: I am nocturnal. B is diurnal.
• At the same moment, islander B has these distinct thoughts: I am awake. A is diurnal.
We want to know: what is the actual type and state of both A and B? Can we know everything about them, or is their something about them that we cannot tell? Or maybe these thoughts are impossible, and lead to contradictions.

To solve these kinds of puzzles, it helps to know the Four Laws of the Isle of Dreams:

1. An islander while awake will believe they are diurnal.
2. An islander while asleep will believe they are nocturnal.
3. Diurnal inhabitants at all times believe they are awake.
4. Nocturnal inhabitants at all times believe they are asleep.
Let's just establish the first law, and then you should try to convince yourself of the others. Consider the case of a diurnal awake islander: because they are diurnal and awake, they think true thoughts, so they will correctly think that they are diurnal. Second, consider the case of a nocturnal awake islander: because they are nocturnal and awake, they will think false thoughts, and will conclude that they are diurnal. So, no matter whether an islander is diurnal or nocturnal, when awake they will think they are diurnal (some correctly, some falsely). Using this along with rule 2, if an islander thinks they are diurnal, you should conclude that they are awake.

Now back to the puzzle:

• Islander A has two distinct thoughts at the same moment: I am nocturnal. B is diurnal.
• At the same moment, islander B has these distinct thoughts: I am awake. A is diurnal.
Applying the four laws of the Isle of Dreams to the first thoughts of the islanders in the puzzle above, we know that A must be asleep (law 2) , and that B must be diurnal (law 3). Now turning to A's second thought: because they are asleep and thinking something that is true (B is diurnal) A must be nocturnal. B's second thought is not true, so since they are diurnal they must be asleep. So, A is nocturnal and asleep, while B is diurnal and asleep. Sweet dreams, A and B.

How many puzzles can we make like this, where we have two islanders, each thinking something about their state or type and something about the state or type of the other? Well, there are 4 possible thoughts an islander could have about themselves (I am awake/asleep/nocturnal/diurnal) and 4 possible thoughts about the other (They are awake/asleep/nocturnal/diurnal), giving us 16 pairs of thoughts. Since there are two islanders involved, this gives 256 puzzles (really only 128 truly different puzzles, as A and B are interchangeable).

You can try out all 256 of them, or as many as you like, here. They look something like this:

This collection of puzzles has some interesting features. There are 192 that are completely solvable: you can find the type and state of both A and B from the thoughts that they think (like the example above). There are 32 partially solvable puzzles, where the first thoughts of A and B (their thoughts about themselves) tell us something about their state and type, but their second thoughts (about the other islander) are inconclusive. Finally, there are 32 puzzles included in the set where the thoughts of A and B are contradictory, and therefore impossible. We can include these contradictory items in the set, as the question page gives you the chance to identify these nasty puzzles.

It turns out that the distribution of the partially solvable and impossible puzzles display an interesting pattern. Let's consider all 16 pairs of thoughts, and make a graph showing which combinations are (a) completely solvable, (b) partially solvable, or (c) impossible.

Here are the 16 pairs of thoughts an islander might have:

1: I am awake. The other is awake.
2: I am awake. The other is asleep.
3: I am awake. The other is diurnal.
4: I am awake. The other is nocturnal.
5: I am asleep. The other is awake.
6: I am asleep. The other is asleep.
7: I am asleep. The other is diurnal.
8: I am asleep. The other is nocturnal.
9: I am diurnal. The other is awake.
10: I am diurnal. The other is asleep.
11: I am diurnal. The other is diurnal.
12: I am diurnal. The other is nocturnal.
13: I am nocturnal. The other is awake.
14: I am nocturnal. The other is asleep.
15: I am nocturnal. The other is diurnal.
16: I am nocturnal. The other is nocturnal.

Let's create a graph where the horizontal axis represents A's thoughts and the vertical axis represents B's thoughts. A white square on the graph represents a completely solvable puzzle for that x/y combination of thoughts, a grey square on the graph represents a partially solvable puzzle, and a black square represents an unsolvable puzzle.

solvable, partially solvable, and unsolvable
Isle of Dreams puzzles

This is really neat: the partially solvable and unsolvable combinations form an interesting pattern dispersed through the whitespace of the completely solvable puzzles. There are 16 "problem squares" of 4 puzzles that have a distinct symmetric pattern, and these 16 problem squares are arranged in 4 sets of 4 puzzles that also have an interesting symmetry.

We'll zoom in on one of the "problem squares" to give a better picture of what the graph is displaying:

Let's look at one of the contradictory puzzles - the one in the bottom left of this "problem square."

A is thinking #1: I am awake. The other is awake.
B is thinking #5: I am asleep. The other is awake.

From their first thoughts, we know that A is diurnal and B is nocturnal. If A is awake, they they will think true thoughts and consequently B is awake. If B is awake, they must be thinking false thoughts, requiring A to be asleep - a contradiction. On the other hand, if A is asleep, they will be thinking false thoughts, so B will be asleep. B will then be thinking true thoughts, requiring A to be awake, again a contradiction.

But why to these partial/contradictory puzzles form the patterns that they do? Maybe we will return again to the Isle of Dreams someday to find an answer.

Try the puzzles out here: https://dmackinnon1.github.io/inspectorCraig/dreamers.html

Sunday, May 6, 2018

more bipartite art

Playing around with some of the images created by connecting two sets of dots. In this case, every dot from the second set is connected to every dot in the first set, and the two sets are arranged in concentric circles. In the picture above, the first set of dots has 12 equally spaced dots in a circle, and the second set has 48, but the second set is arranged on a circle whose radius is much, much larger than the first, so the lines from the second set to the first come in from a great distance.

If both sets have 3 dots, both sets are on concentric circles, and one of the sets is on a much larger circle, you might get something like this:

The second set is so far out, that it looks like the lines from a point the second set are parallel. If the first set has 3 points and the second far-out set has 6 points, you might get something like this:

Increasing size of the far-out set to 18 points:

Can you figure out the number of points in each set that would generate an image like this? You can test out your guesses here.