## Thief-turned-teacher

A mathematics teacher narrated the most important story of his life to his students one day, "Seven years ago, I was sentenced to an unusual punishment after having been convicted of theft. I was taken to a closed space with many doors in front of me. I was told that all but one of them had hungry lions behind them. If I could open the one without a lion behind it, I would be free. If I opened the wrong door, I would be killed."

He continued, "Only the king knew which one of those doors would lead me to freedom. He allowed me to ask two yes-no questions under the condition that if I managed to get out that place alive, I would have to serve his kingdom as a mathematics teacher for the rest of my life. The king promised me that he would answer both the questions truthfully if he knew the answers. In case he didn't know the answer to a question, he would clearly say so. I was vey lucky. The number of doors was just right. Had there been one more door, I might not have got out of that place alive."

What two questions might he have asked?

[SOLVED]

#### Alex Yeilding solved this puzzle:

There are three possible answers to each question asked of the King: "Yes", "No, and "I don't know".

If we can figure out questions that give all those answers, we can differentiate among 9 doors.

Here is one scheme.
On three of the doors paint "Is 1 + 1 = 2?"
On another three, paint "Is 2 + 2 = 5?"
On the final three, paint "Is the answer to this question 'No'?"

Then ask question 1: "Is the answer to the question on the door that leads to safety 'Yes'"?

If the king answers "yes", you are dealing with one of the first three doors. If "no", the second set, and if "I don't know", the 3rd set.

Erase the questions on two of the possible doors, and replace them with the other questions above, so that you have each question appearing on one of the three possible doors, then repeat the question to the king to determine which door to walk through.

If there were more than 9 doors, then at least one set of kingly answers leaves you wondering which door to choose.

If you think the king will not answer the paradox question appropriately, you could count on his not being omniscient, and ask him if Brazil will win the first World Cup of the next century, or maybe borrow a statement from Professors Godel or Heisenberg.

#### Lawrence E. Flynn solved this puzzle:

There are nine doors. First question: Is the no-lion door one of four doors, namely doors 1, 2, 3 and a door I've selected from doors 4, 5 and 6?

Yes ⇒ 1, 2 or 3 is the no-lion door.
No ⇒ 7, 8 or 9 is the no-lion door.
Don't know ⇒ 4, 5 or 6 is the no-lion door.

Second question (taking 1, 2 and 3 case without loss of generality): Is the no-lion door one of two doors, namely door 1 or a door I've selected from doors 2 and 4?

Yes ⇒ Open door 1.
No ⇒ Open door 3.
King doesn't know ⇒ Open door 2.

#### James Dow Allen commented:

Alexy's solution works except for the possible objection that a question about the answer to an improperly-formed question is itself improperly formed.

Here's a way to choose the safe door of three without improperly formed questions:

"Is it the case that a lion behind Door B implies both Goldbach's Conjecture and that there is a lion behind door C?"

#### Susam Pal from cotpi added:

Here is another way to solve the problem without requiring the prisoner to rely on paint or unproven conjectures. This is similar to Lawrence's solution that sets the prisoner free even if the king has secretly proved or disproved the conjecture.

Partition the group of 9 doors into 3 groups of 3 doors each. Number them 1, 2 and 3. The first question by the prisoner could be, "I have a number in my mind that is either 2 or 3. Is the group number of the group containing the safe door less than the number in my mind?"

If the king says, "Yes", group 1 has the safe door. If the king says, "I don't know", group 2 has it. If the king says, "No", group 3 has the safe door.

Select the doors in the safe group and number them 1, 2 and 3. Now, the second question by the prisoner could be, "Is the door number of the safe one less than the number in my mind?"

If the king says, "Yes", door 1 is safe. If the king says, "I don't know", door 2 is safe. If the king says, "No", door 3 is safe.

We can prove that if there had been one more door, the prisoner could not have determined the safe door with certainty.

There are three possible answers for each question. So, the prisoner gets log2(3) bits of information from the answer to each question. To find one safe door out of n given doors, he needs log2(n) bits of information, where n is a positive integer. So, the following must hold true.

log2(n) ≤ 2 · log2(3)
⇔ log2(n) ≤ log2(32)
⇔ n ≤ 9

So, the number of doors must have been less than or equal to 9 for the prisoner to have successfully determined the safe door with certainty.

### Credit

This puzzle is based on:

The following is a list of resources on related topics: