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.



Friday, April 27, 2018

some Chessboard Puzzle solutions

In the previous post I mentioned some mathematical chessboard puzzle puzzles, created as part of working through the book Across the Board, by John J. Watkins. This post provides some possible solutions to the puzzles on that puzzle page.

Queens on a 5 by 5 board

The puzzle "Place 3 queens on a 5x5 chessboard. The board must be dominated," is asking you to find the minimal dominating set for queens on a 5x5 board (3 is the queen's domination number for 5x5 boards). Here are two solutions:

The large dots show where the queens are placed, and a small dot appears on every square that is reachable by a queen. In the solution on the left, all three queens can be attacked, but in the solution on the right, the queen in the corner is uncovered.

The puzzle "Place 5 queens on a 5x5 chessboard. The board must be dominated. The pieces must be independent," is asking you to find the maximal independent set for queens on a 5x5 board (5 is the queens independence number for 5x5 boards). Here's a solution:


There is also a puzzle that asks you to find an arrangement between the domination and independence numbers, "Place 4 queens on a 5x5 chessboard. The board must be dominated. The pieces must be independent." Here is one solution for that:



Queens on other boards

On a 6x6 board, our queen puzzles will be bounded by the domination number of 3 and the independence number of 6. Here are solutions for those:


In between these, we have "Place 5 queens on a 6x6 chessboard. The board must be dominated. The pieces must be independent;" here's a solution for that one:


Just to get a sense of what solutions to these might look like in general, let's jump up to 8x8. In this case, the domination number for queens is 5, so the puzzle in our set with the fewest queens on 8x8 is "Place 5 queens on a 8x8 chessboard. The board must be dominated. The pieces must be independent." Here is one solution:


This particular solution is of interest because the pieces are in a pattern known as the Spencer-Cockayne construction, which can be used to find coverings of square boards of side length 9, 10, 11, and 12 as well. More interesting details can be found in Across the Board.

Knights on a 5x5 board

There are plenty of "independence and domination" problems for the knight on a 5x5 board, because the gap between the domination number (5) and the independence number (13) is so large (compared to queens on the 5x5, at least). Finding solutions for some of the intermediate numbers is a bit tricky, you may find. 


For example, here is a solution to "Place 9 knights on a 5x5 chessboard. The board must be dominated. The pieces must be independent":


Knights on other boards

All puzzles based on the maximum number of independent knights on a board have the same solution: put a knight on every square of the colour that has the most squares (on odd boards, one colour has more squares than the other). 


Here is an example of a puzzle based on a "sub-optimal" dominating set that is also independent: "Place 11 knights on a 6x6 chessboard. The board must be dominated. The pieces must be independent." And a solution:


Bishops on 5x5

Of the remaining pieces that we have puzzles for, bishops, kings, and rooks, the bishop is the most interesting, and the 5x5 board gives a good idea of how to construct the puzzle solutions.

Consider these two puzzles:

"Place 5 bishops on a 5x5 chessboard. The board must be dominated. The pieces must be independent."

"Place 8 bishops on a 5x5 chessboard. The board must be dominated. The pieces must be independent."


The minimum dominating set for bishops on a 5x5 board has 5 pieces, and the maximum independent set has 8. In between these, we can also form puzzles based on non optimal dominating sets (that are also independent), such as:

"Place 6 bishops on a 5x5 chessboard. The board must be dominated. The pieces must be independent."

"Place 7 bishops on a 5x5 chessboard. The board must be dominated. The pieces must be independent."


Solutions for finding similar solutions for bishops on boards of other sizes follow the same patterns as those on the 5x5 board.

Hopefully, these examples will help you out if you get stuck on any of the puzzles. As mentioned earlier, if you are interested in learning more about the mathematics behind these puzzles, check out Across the Board.


Related posts and pages
domination and independence puzzles 
post introducing chessboard puzzles
chess tour puzzles
post on chess tour puzzles


Tuesday, April 24, 2018

Mathematical Chessboard Puzzles

Chess problems are compositions where a set of pieces are arranged as if in a game and a specific goal is set - the problem is to determine how to get from the arrangement to the end goal. An interesting variation on the traditional chess problem are the retrograde analysis chess problems of Raymond Smullyan, where instead of a goal being set, a question is asked about the conditions that may have lead to the arrangement (a backwards looking problem, rather than the traditional forwards looking type). Mathematical chessboard problems are completely different than these traditional chess problems, and bear little connection to the actual game of chess - they are more concerned with the structure of how particular pieces can move on the board, and ask questions about how a single piece can move about the board, or about what positions are reachable by collections of the same type of piece. These problems are questions in graph theory in (thin) disguise, and have attracted the attention of both professional and recreational mathematicians.

A useful and very readable guide to mathematical chessboard problems is Across the Board, by John J. Watkins. I’ve been playing around with knight tours for a few years, and since picking up this book a while back, I have been returning to it again and again to learn new and interesting things about them. Although I had heard about other mathematical chessboard problems, like the eight queens problem, Across the Board introduced me to the general category of chess independence and domination problems and encouraged me to learn more about them.

A group of chess pieces of the same type is said to dominate a board if every square is either occupied or a neighbour (reachable in one move) of an occupied square. A group of chess pieces of the same type is said to be independent if no piece is a neighbour of any other piece. Domination (sometimes called covering) problems are, generally, to find a minimal dominating set, for example, the smallest number of queens required to dominate a board. Independence (or un-guarding) problems generally require you to find a maximal set of pieces that can be placed and remain independent; the greatest number of knights, for example, that can be placed so that no knight attacks another.

Uninteresting examples of dominating queens and independent knights.
A minimal dominating set and a maximal independent set would be more interesting

As part of working through Across the Board and understanding chess domination and independence, I tried to create an interactive ‘mathematical chessboard puzzle’ set (try it out here). Here is a screenshot example:

An example puzzle from the online set.
 The solver is not off to a good start.

What is the difference between a mathematical chessboard problem and a mathematical chessboard puzzle? When considering the problem of queens independence, we would expect a serious treatment: a solution which finds the maximum number of independent queens for boards up to a certain size, an algorithm or method for generating maximal independent arrangements, and for some cases that remain unsolved by methods provided, some way of placing bounds on the independence number. A puzzle based on the idea of queens independence is a much simpler thing: merely an instruction like “Find a way to place 8 queens on an 8x8 board so that the board is dominated and the queens are independent.” Across the Board provides a great survey of results that mathematicians have used in tackling the problems of finding dominating sets, independent sets, and tours. The rest of this post is about puzzles (like the example above) that are generated from those results.

In puzzles inspired by the problems of domination and independence, we want to ask the solver to come up with arrangements of pieces of a single type, constrained so that the pieces either dominate the board, are independent, or both. Recall that the domination problem is looking for a minimum number of pieces required to cover the board (either by placement or by attack), while the independence problem is looking for a maximum number of pieces that can be placed independently. For example, for queens on a 5x5 board, the domination number is 3, but the independence number is 5. So for queens on a 5x5 board, our puzzles will require placements of sets ranging from 3 to 5 queens.

There is an asymmetry between domination and independence that we have to keep in mind: A solution to the domination problem might not be independent, but the maximal independent set will always be dominating. The example of 3 queens on the 5x5 board shows that you cannot always make your dominating set independent. On the other hand, a maximal independent set will always dominate: if the set does not dominate the board, that means there is a square that cannot be attacked by any of the current pieces - you can therefore add one more piece to the board at that spot, contradicting the fact that you already had a maximal independent set.

For our puzzles, we’ll just consider boards from 4x4 to 8x8 (so that they fit reasonably on the screen). In the table below, the lowest number in each cell represents the domination number for that piece on the given board size, and the largest represents the independence number. The letters next to each number indicate whether the set of that size should be said to be independent (i) and/ or dominant (d) - some of this information is redundant, but all indicators are included for completeness. The numbers between the least and greatest represents other possible arrangements. For example, for queens on a 4x4 board, the domination number is 2 (dominant set is not independent in this case), and the independence number is 4, but it is possible to find a dominating independent set of size 3, giving us the entries 2d, 3di, and 4di.


The independence and domination numbers in the table above are from the results described in Across the Board; the values between were found looking at the solutions for either domination or independence and perturbing them slightly. For example, to fill in the values for queens on an  8x8 board, start with one of the solutions to the queens domination problem for 8x8, which consists of an arrangement of 5 pieces, and move one of the pieces to a reachable square with fewer neighbours, and fill in the gaps with additional pieces. Proceeding by trial and error, this leads to dominating independent sets of 6 and 7 pieces. Finding additional dominating and independent sets for knights is a little more challenging than others - there are some gaps in the table (maybe you can fill them). Most of these possible puzzles were written out in a format for displaying online, which you can view here.

If you interested in exploring the mathematical chessboard problems through the playful medium of chessboard puzzles, please give these a try; if you are interested in learning more about the mathematics behind these puzzles, check out Across the Board.

domination and independence puzzles: https://dmackinnon1.github.io/chessdom/puzzles.html
chess tour puzzles: https://dmackinnon1.github.io/kixote/

some puzzle solutions

Wednesday, March 7, 2018

Symmetry and Asymmetry in Tigers and Treasure

Tiger and treasure logic puzzles, like ones you can try out here,  offer you a choice between two doors that might lead to treasure, or a tiger. Statements on "door 1" are true only if they lead to treasure, and statements on "door 2" are true only if they lead to a tiger.

The previous post gave an overview of the different "tiger and treasure" logic puzzles that could be formed from a starting list of 14 statements:
  1. this room has treasure
  2. the other room has treasure
  3. at least one room has treasure
  4. both rooms have treasure
  5. this room has a tiger
  6. the other room has a tiger
  7. at least one room has a tiger
  8. both rooms have a tiger
  9. this room has treasure or the other room has a tiger
  10. the other room has treasure or this room has a tiger
  11. this room has treasure and the other room has a tiger
  12. the other room has treasure and this room has a tiger
  13. both rooms have treasure or both rooms have a tiger
  14. one room has treasure and the other has a tiger
All possible puzzles are listed here (statement numbers in the file start at 0, rather than 1).

When exploring all the different possible puzzles we can make from these, we won't include puzzles that lead to a contradiction, or puzzles where the clues don't allow you to identify either door. This leaves 96 good puzzles out of the 196 combinations of statements, shown in black below:


Symmetry among Puzzles

For each statement in the list of fourteen, you can find the negation of that statement in the list - for example, statement 1 "this room has treasure" has its negation in statement 5 "this room has a tiger." If we plot the list of statements on door 1 vs. the the list of statements on door 2, but re-arrange the statements on the door 2 axis so they are the negations of our original list (the negated list would be statements 5, 6, 8, 7, 1 ,2, 4, 3, 12, 11, 10, 9, 14, 13), we can see the symmetry in these puzzles more clearly:


This graph is  telling us that if we have a puzzle that works, then if we swap the signs on the doors and negate them, we will also get a working puzzle. If you explore this a bit further, you'll see that the symmetry goes deeper. Let's get a  little mathy with this.

If a and b are statements in our list, a puzzle P can be described by the ordered pair (a,b). Every puzzle P also has a solution, (s, t) where s and t are either "tiger", "treasure", or "unknown."

For any statement in the list x, we can write the negation of x as -x. If we form a new puzzle by putting the negation of a on door 2 and the negation of b on door 1, we get a new puzzle -P = (-b,-a).

The symmetry of our tiger treasure puzzles can be expressed as this little theorem:
If P = (a,b) is a tiger treasure puzzle with solution (s,t), then its negation, -P = (-b, -a), will have the solution (t, s).
Here is an example. Consider the example puzzle from the previous post.

Puzzle P
Door 1 says: Both rooms have a tiger. (statement 8)
Door 2 says: The other room has treasure and this room has a tiger. (statement 12)

In the previous post, we worked out that door 1 has a tiger and door 2 has treasure.

Statement 8's negation is statement 3, and statement 12's negation is statement 9. So the puzzle -P looks like this:

Puzzle -P
Door 1 says: This room has treasure or the other room has a tiger (statement 9) 
Door 2 says: At least one room has treasure (statement 3)

If you have tried out a few of these, you may be able to find the solution to -P, which is that door 1 has a tiger and door 2 has treasure, which is the reverse of Puzzle P, where door 1 had treasure and door 2 had the tiger - the contents behind the doors have switched.

The symmetric graph above helped point us towards a nice symmetry that holds true for all of the tiger and treasure puzzles, but our original non-symmetric graph can point to another interesting things too.


Using asymmetry to make puzzles more interesting

In Raymond Smullyan's book "The Lady or the Tiger?" he presented a nice twist on the usual presentation of this kind of puzzle:
"There are no signs above the doors!" exclaimed the prisoner. "Quite true," said the king. "The signs were just made, and I haven't had time to put them up yet." "Then how do you expect me to choose?" demanded the prisoner. "Well, here are the signs," replied the king. That's all well and good," said the prisoner anxiously, "but which sign goes on which door?" The king thought awhile. "I needn't tell you," he said. "You can solve this problem without that information."
Let's look around for puzzles like this. One question to ask: Which of our problems would allow us to interchange the signs on the doors without affecting the solution to the problem? We'd like to know when does P = (a,b) give the same solution as Q = (b,a)? To explore which puzzles might work in this way, we can start looking at our first graph above, but limit our attention to those puzzles who's reflection in the line door1= door2 is also a puzzle. These are shown in black below (grey shows other puzzles whose reflection is not also a puzzle).


But we don't just want puzzles whose reflection gives us a puzzle, but ones whose reflections have the same solution as the original. It turns out that this gives an uninspiring set of six puzzles:


Only the trivial cases work: puzzles where the statements on the doors are exactly the same end up giving us puzzles that have exactly the same solution when the statements are interchanged. So what about the problem from "The Lady or the Tiger?", it uses these statements:
  • this room contains a tiger  (statement 5)
  • both rooms contain tigers (statement 8)
Why does the solver not need to know which door each goes on? Well, if statement 5 goes on door 1 we get a contradiction, so it must go on door 2. This is why the solver does not need to be told how to label the doors: there is only one possible way to do so without getting a contradiction. So, a way to find more problems like this is to look for puzzles P = (a,b) where P is a legitimate puzzle, but Q = (b, a) is not a puzzle, as that labelling of the doors leads to a contradiction.



There are 32 puzzles in this category (shown in black above): puzzles when you exchange the statements on the doors, you obtain a contradiction. Adding to this the 6 trivial cases where both doors have the same statement, we have 38 puzzles where we simply present the statements without explaining which statement is on each door.

For example, the puzzle (13, 10) falls into this set.

Let's try putting 13 on door 1 and 10 on door 2:

door 1: both rooms have treasure or both rooms have a tiger (13)

door 2: the other room has treasure or this room has a tiger (10)

Because inscriptions on door 1 are only true of door 1 leads to treasure, statement 13 implies that door 2 must lead to treasure. Door 2 leading to treasure makes its statement (10) false, requiring door 1 to lead to a tiger.

However, if we switch the statements, we run into trouble:

door 1: the other room has treasure or this room has a tiger (10)

door 2: both rooms have treasure or both rooms have a tiger (13)

If statement 10 on door 1 is false, then door 1 would lead to a tiger. However, the statement says that it leads to a tiger, so this cannot be. Door 1 must lead to treasure, making statement 10 true, requiring door 2 to also lead to a treasure. If door 2 leads to treasure, then its statement (13) must be false. However, statement 13 is true (both rooms have treasure), a contradiction.

So, presented with statements 10 and 13, there is only one way to arrange them on the doors: put statement 13 on door 1 and statement 10 on door 2, leading to a tiger behind door 1 and treasure behind door 2.

Please try out the tiger-treasure puzzles here and ask yourself: "What would the negation of this puzzle (-P) be?" and "Is this one of the 38 puzzles that can be answered without being told which sign is on which door?"

Friday, March 2, 2018

Tigers and Treasure

Here is yet another type of logic puzzle for you:
Imagine there are two doors, both doors either lead to a tiger or treasure. You would like to know what each door leads to. On each door there is an inscription that provides a clue. If door 1 leads to treasure, its inscription is true, otherwise it is false. If door 2 leads to a tiger, its inscription is true, otherwise it is false. 
Door 1 says: Both rooms have a tiger.
Door 2 says: The other room has treasure and this room has a tiger. 
Can you figure out what each door leads to?

Here is one way to think about it:

Door 1 cannot lead to treasure, since if it does its inscription must be true. The inscription on door 1 contradicts the assumption that it leads to treasure. Consequently, door 1 must lead to a tiger. However, if door 1 leads to a tiger, its inscription must be false - which means the statement "both rooms have a tiger" cannot be true, so door 2 must lead to treasure. If door 2 leads to treasure, then its statement is false, which lines up with door 1 having a tiger and door 2 having a treasure. If we instead start with the inscription on door 2, if door 2 had a tiger, it would mean that door 1 has a treasure, but door 1 leading to treasure leads to a contradiction. It is safe to conclude that door 1 leads to a tiger, and door 2 leads to treasure.

You can find 96 of these puzzles here.

These puzzles, like previous ones are based on puzzles by Raymond Smullyan. In this post, I wanted to look at a reasonable list of statements that could appear on the doors, and how the statements interact with the peculiarities of the doors.

To generate these puzzles, I started with a set of 14 statements that could be placed on either door:

  1. this room has treasure
  2. the other room has treasure
  3. at least one room has treasure
  4. both rooms have treasure
  5. this room has a tiger
  6. the other room has a tiger
  7. at least one room has a tiger
  8. both rooms have a tiger
  9. this room has treasure or the other room has a tiger
  10. the other room has treasure or this room has a tiger
  11. this room has treasure and the other room has a tiger
  12. the other room has treasure and this room has a tiger
  13. both rooms have treasure or both rooms have a tiger
  14. one room has treasure and the other has a tiger

If we stick with puzzles generated using these 14 statements, there are 196 possible labelling of door 1 and door 2. However, some statements will not work on a particular door. For example, door 2 cannot be labelled with statement 1, since if door 2's statements are only true if door 2 leads to a tiger, the statement  "this room has treasure" will lead to a contradiction in every case. If door 2 has a tiger, then its statements are true, but "this room has treasure" would be false. If door 2 has treasure, then its statements are false, but "this room has treasure" would be true.

The graph below shows all 196 possible puzzles. The puzzles that lead to contradictions are coloured as white squares, the puzzles that do not lead to contradictions are coloured in black. We can see a white strip across the bottom: these are all the puzzles where door 2 is labelled with statement 1. Can you find the statement that always leads to contradictions for door 1? There are 131 puzzles that are "good" in the sense that they do not lead to contradictions.

treasure/tiger puzzles with solutions,
or an upside-down DigDug level

But some of these 131 puzzles are not so satisfying - the clues provided on the doors don't help in figuring out what lies beyond. In some cases, like the example puzzle above, the clues will tell you what lies beyond both doors. In others, you may only learn the contents of one door. For certain puzzles, you can conclude nothing. There are 35 puzzles, shown in black below, that are contradiction-free, but whose clues provide inconclusive information about the rooms.

treasure/tiger puzzles where the inscriptions
tell you nothing

In the graph above, notice that many puzzles along the vertical stripe at statement 1 are in this category of puzzles that tell us nothing. When put on door 1, the statement "this room has treasure" is not helpful (except in some interactions with door 2 statements); taken on its own, if door 1 has treasure, the statement is simply true, and if door 1 does not have treasure, it is simply false - it does not tell us anything about door 2's possible contents, or generate a contradiction that would allow us to reject one of the options. Similarly, the horizontal stripe at statement 5 symmetrically corresponds to door 2 having the statement "this room has a tiger."

So, to get a set of nice puzzles, we take the 131 that are contradiction-free, and remove these 35 unsatisfying puzzles to obtain 96 where you can find the contents of at least one of the rooms based on the inscriptions on the doors.

Some of the puzzles are particularly nice: both rooms lead to treasure! There are 20 of these, shown in black below:

treasure/tiger puzzles with two treasures

A quick look at this graph shows that when statement 11 is on door 2, or when statement 10 is on door 1, your odds of getting treasure are pretty good.

Looking at statement 11:
this room has treasure and the other room has a tiger
If seen on door 2, we know it cannot be true: statements on door 2 are only true if door 2 leads to a tiger. So this means two things: First door 2 must have treasure, and second, the statement is false. The only way for the statement to be false is if door 1 also leads to treasure.

Looking at statement 10:
the other room has treasure or this room has a tiger
If seen on door 1, this statement cannot be false: statements on door 1 are only false if door 1 leads to a tiger. If door 1 leads to a tiger, this would make the statement true - a contradiction. So this means two things: door 1 must lead to treasure, and the statement must be true. The only way for the overall statement to be true is if door 2 also leads to treasure.

Statements 11 and 13 are, just like statements 1 and 3, negations of each other. DeMorgan's laws, tell us that an "and" statement like "this room has treasure and the other room a has a tiger" when negated becomes an "or" statement, like "the other room has a treasure or this room has a tiger."

Just as there are puzzles that lead to 2 treasures, there are those that lead to two tigers. Not surprisingly, there are 20 of these also, and their graph looks like this:

treasure/tiger puzzles with two tigers

Can you see why statement 9 when put on door 2 leads to two tigers, and why the same is true for statement 12 when put on door 1?

Although some puzzles end up being solvable with two tigers or two treasures, the classic form of the puzzle would have a solution where we would find a tiger behind one door, and treasure behind the other. It turns out there are 40 of these in our set, distributed like so:

treasure/tiger puzzles where the
solution is one of each

Rounding out the puzzle collection are puzzles with one door that is unknowable. There are 16 of these, with 8 puzzles having a solution that is a tiger plus an unknown and 8 that is a treasure plus an unknown.

So, out of the 196 combinations of our 14 statements on two doors, we have 131 that are contradiction free. Of these, we removed the 35 where the clues do not allow you to draw any conclusions about the rooms. This leaves:
- 16 puzzles that have a partial solution (8 where one door leads a tiger, and another 8 where one door leads to treasure);
- 40 puzzles that have one door leading to a tiger and one to treasure;
- 20 puzzles that have both doors leading to tigers; and
- 20 puzzles that have both doors leading to treasure.

See how many you can solve: https://dmackinnon1.github.io/inspectorCraig/tiger.html

Update: Another post about tigers and treasure puzzles

Sunday, February 4, 2018

Inspector Craig, Logical Detective

Inspired by the puzzles of Raymond Smullyan, I've been playing with various puzzle types that he either invented or popularised. Earlier I posted some knight and knave puzzles, and a a page of puzzles inspired by his "Portia's Caskets" puzzles, and now another has joined the pile: The Case Files of Inspector Craig.

Here's an example of the kind of puzzles you will find on the page:


Your goal is to classify each suspect as either innocent, guilty, or unknown (in the case where the evidence cannot support either guilt or innocence).

Depending on how familiar you are with logical symbols, it may help to simplify the language used to describe the clues - if we use the letter X to mean "X is guilty," we can express the statements above a bit more formally:

There are two key techniques for solving these puzzles: 1) start with one of the statements, say A, and see if applying the propositions will lead to a contradiction; and 2) start with the statement "A or B or C" and work out the implications of each case - if there is a result that all three lead to, then that must be true.

We can use the first method starting with B. If we assume B is guilty then since B always uses A as an accomplice (B implies A), A must be guilty. However we also have a statement that says that A never works with B (A implies not B), which means that B is innocent. Since assuming B is guilty ended up showing that B is innocent (B implies not B), then B must not have been guilty.

Using the second method, we know that either A or B or C is guilty. We already know that B is innocent, so that leaves us with A and C. If A is guilty, we can't determine much else. However if C is guilty, then since C always uses A as an accomplice (C implies A), then A is also guilty. So, no matter which of the two alternatives we choose, A is guilty.

Unfortunately, there is no way to know whether or not C is guilty based on this reasoning, so we are left to make this selection:


Which turns out to be correct.

Try a few out here: https://dmackinnon1.github.io/inspectorCraig/

Saturday, January 13, 2018

bipartite art

A bipartite graph consists of two sets of nodes, N and M, where every node in N is connected to every node in M by an edge.

If you set up the nodes N and M on a pair of circles centred around the same point, you can get quite a variety of nice looking diagrams. As part of playing around with generating svg images using d3js, I set up a page that allows you to create some 'bipartite art.' Some of the diagrams turned out nicely, particularly when you hide the nodes completely:






Try it out at: https://dmackinnon1.github.io/bipartite2.html