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