17
$\begingroup$

A (hopefully) new variant on the Knights & Knaves problem.

On the island of D'Israel, the inhabitants fall into three types: Liars, Damned Liars, and Statisticians. They are visually indistinguishable except that each type of person wears a different colour of hat. If you ask them questions, their responses are as follows:

  • a Liar will always give you a false response
  • a Damned Liar will give you a false response and also stab you
  • a Statistician will give you a true or false response with 50% probability.

You are trying to escape from a prison on this island, and you are nearly out when you reach a row of three doors, each one guarded by a solid-looking sentry. The three sentries wear red, green, and blue hats, so you know that one is a Liar, one a Damned Liar, and one a Statistician, but you don't know which is which. You also know (from the prison map which was smuggled in to you and which you have now lost) that one of the doors leads to freedom, one to the prison warden's office, and one to a first-aid room; but again you don't know which is which. Your aim is to pass through the door that leads to freedom, but if you are stabbed by the Damned Liar, you will first need to visit the first-aid room. If you go to the warden's office, you will be recaptured; but going through either of the other doors allows you the chance to double back and try again if necessary.

You are being pursued, so you only have time to ask the guards one yes/no question to find out which door you should go through. What question should you ask? What is the probability you will escape?

How does the answer change if you have time for two or three questions?

This is a logic puzzle. Please, no lateral-thinking answers.

$\endgroup$
  • 3
    $\begingroup$ Knights & Knaves combined with Monty Hall? $\endgroup$ – JNF Mar 15 '15 at 12:00
  • 1
    $\begingroup$ If you pick the door to freedom but need the first-aid room, are you allowed to double back and pick again? $\endgroup$ – Ben Aaronson Mar 15 '15 at 12:05
  • 1
    $\begingroup$ Oh, and do the questions have to be yes-or-no? $\endgroup$ – Ben Aaronson Mar 15 '15 at 12:06
  • $\begingroup$ @BenAaronson Thanks for your feedback! I've edited the question. $\endgroup$ – Rand al'Thor Mar 15 '15 at 12:12
  • 1
    $\begingroup$ @JNF puzzling.stackexchange.com/q/3116/5373 ;-) $\endgroup$ – Rand al'Thor Mar 15 '15 at 12:13
7
$\begingroup$

I am able to escape without risk.

Using so called head exploding questions we can extract even more that one bit of information from the guards. In this example, we will produce a paradox if the ward is behind the second door. I.e., we ask a liar “Will you answer yes?”. If she answers “Yes” than she is telling the truth, that isn't allowed and if she answers “No” then she is telling the truth as well.

Exploiting self-referential statements can also persuade the statistician to give a useful answer. (We won't know whether we got lied to or not, but we don't care about that.) This is possible because of your wording “a Statistician will give you a true or false response with 50% probability.” instead of “a Statistician will give you a random response.”

So here is the question:

Is your statement a lie and not

door a = ward or

(door b = ward) and (is your answer no)

or is your statement true and

door a = ward or

(door b = ward) and (is your answer no)

Or with more math notation, we ask to evaluate $$ ((\lnot t) \land \lnot(a \lor (b \land p))) \lor (t \land (a \lor (b \land p)))\text{,}$$ where $t$ indicates if a guard tells the truth, $a$ and $b$ ask whether the ward is behind the respective door, $r$ the answer which will be given and $p = (r == \text{No})$ produces the paradoxes to explode heads.

With a small table we can work out that if a guard answers “No” than the ward is behind the a door, if the guard answers “Yes” than the ward is behind the c door and if her head explodes the ward is behind b.

Here is a table of all possible states of the world: τ r a b | True answer | Response 0 0 0 0 | 1 | 0 0 0 0 1 | 0 | 1 -> head explodes 0 0 1 0 | 0 | 1 0 1 0 0 | 1 | 0 0 1 0 1 | 1 | 0 -> head explodes 0 1 1 0 | 0 | 1 ……………………………………………………………………………………………………………… 1 0 0 0 | 0 | 0 1 0 0 1 | 1 | 1 -> head explodes 1 0 1 0 | 1 | 1 1 1 0 0 | 0 | 0 1 1 0 1 | 0 | 0 -> head explodes 1 1 1 0 | 1 | 1

$\endgroup$
  • $\begingroup$ Wow, awesome answer! Again I'll need some time to work through your reasoning. $\endgroup$ – Rand al'Thor Mar 15 '15 at 23:13
  • $\begingroup$ Head-exploding questions are sufficiently passé that logic questions should perhaps have a qualifier that specifies that entities asked a question will either nod affirmatively or do nothing. $\endgroup$ – supercat Apr 30 '15 at 21:16
6
$\begingroup$

If we ask the statistician a question, we receive no new information, so regardless of our strategy, we cannot escape more than $1/2$ of the time if we ask him.

If we ask the damned liar a question, we will know the answer to our question (negated), and we will also be stabbed (a painful bit of information). Then, we essentially need to guess which door is the wardens correctly, and check the other two; at best, we can ask "Is this door the warden's?" for some given door and if so (probability $1/3$ - remember that we receive "no" as the answer in this case), we escape, and if not (probability $2/3$), we have a 50-50 shot. Thus, our best case with him is a $2/3$ chance of escape.

If we ask the liar a question, we will know the answer to our question and merely need to guess the escape before the warden's door. The question "Is door $1$ the warden's, or is door $3$ the escape?" suffices, since if we get a "no", then we try door $3$; if it's not the escape, then door $1$ is the warden's, so we escape by door $2$. If we get a "yes", then we try door $1$ - if it's not the escape, then door $2$ must be the escape, so we escape that way.

Putting this together, our best strategy is to a random sentry:

Is either of the following statements true:

You are the liar and either door $1$ is the warden's or door $3$ is the escape.

You are the damned liar and door $1$ is the warden's.

If we receive a "no", try door $3$ then $2$. If we receive a "yes", try door $1$ then $2$. Our probability of escape is easily computed as $\frac{13}{18}$ and this is the best we can do.

$\endgroup$
  • $\begingroup$ I'm still working out what happens if we have multiple questions; my intuition is to ask the same thing of multiple sentries, but I'm not sure. $\endgroup$ – Milo Brandt Mar 15 '15 at 15:55
  • 1
    $\begingroup$ Impressive answer! I'll need to come back later to work out all the probabilities and check the 13/18 figure. Can you prove that this is the best we can do? $\endgroup$ – Rand al'Thor Mar 15 '15 at 16:48
2
$\begingroup$

Asking "what would you/he say?" doesn't give me information on the doors, so we'll rule that out.

We can ask one at random "are you guarding the exit?"

1/3 we're stabbed, so we know the answer is false. Yes - bet on that door as first aid. Get caught or succeed (50:50). If succeed choose one of the others at random (50:50 again). No - that's it. Choose a different one by random for first aid(1/2), and leave.

Total 1/3*(1/2*1/2+1/2)=1/4 success.

2/3*3/4=1/2 false answer without stab. Yes - choose another at random. If it's the the first aid, go back and choose the other. No - take that one

Total 1/2*(1/3*1/2+1/3+1/3) = 5/12 success

1/6 chance of getting a truthful answer, don't bet on it.

I got a total of 8/12 for a healthy getaway

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.