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