99 doors to death!

Question

You wake up in a small locked room of a huge castle. There are 100 doors, numbers 1 to 100, and you are to open one of them. Open the correct door, and the entire castle is yours to keep. Open any of the other 99 doors, and a hungry monster devours you instantly.

There are 100 guards, one in front of each door. You know that 50 of them are truth-tellers, and 50 are liars. You may ask them yes-no questions, but there's a catch: every time you ask a question, the guard will toss a biased coin, with a 0.95 probability of landing on heads. If the coin lands on tails, an alarm will be triggered and the monsters will break through the doors to devour you.

Given that you use the optimal strategy, what is the probability that you will survive and win the entire castle?

Note: Constraints are as follows:
1. You can ask a guard only a boolean question, i.e. which has a 'Yes' or 'No' as the answer.
2. You can not run from the castle.(Not killing the optimistic approach)
3. You can't ask a question, answer to which is not known to guards like "Am I x years old?" or "Am I holding three fingers behind my back?" They will, probably, kill you for wasting their time.

The source of the problem : Brilliant.org

Answer 1

The formulation

If I were to ask you ____, would you answer affirmatively?

can get an honest answer for any yes-or-no question. So now we just have to find the best way to use the questions.

It is never optimal to choose a door until it is the only possibility left, because the chance of survival will always be better after asking a yes-no question (approximately halving the number of possibilities, so doubling the chance of survival with only a 5% penalty).

Now suppose that there is a system of questions such that it can always be narrowed down to one door (possibly choosing different questions depending on the response to previous ones). Each door can be uniquely identified by what sequence of yes/no answers leads to that door. The sequence of answers cannot start with the sequence of a different door, otherwise that door would already have been chosen. Therefore the sequences of answers form a prefix-free encoding of the doors.

Let the length of the code for door $i$ be $l_i$. If the safe door is $i$, it takes $l_i$ questions before choosing that door, so the probability of survival is $0.95^{l_i}$ This make the total probability of survival $\frac{1}{100}\sum_{i=1}^{100}0.95^{l_i}$. We want to maximize this value, under the constraint that $\sum_{i=1}^{100}0.5^{l_i}\le1$ (this is required for it to be a prefix-free encoding, since a code of length $l$ takes up $0.5^l$ of the code space).

If $\sum_{i=1}^{100}0.5^{l_i}<1$, there is some wasted sequence that does not match any door. This can only happen if some question is being asked in some situation where only one answer is possible. That question can be skipped to improve the chance of survival, so we can assume that $\sum_{i=1}^{100}0.5^{l_i}=1$.

Let the smallest $l_i$ be $m$ and the two largest ones be $n$ (there must be at least two tied for largest for the condition $\sum_{i=1}^{100}0.5^{l_i}=1$ to be true). Suppose $m+2\le n$. Then $$0.5^{m+1}+0.5^{m+1}+0.5^{n-1}=0.5^{m}+0.5^{n-1}=0.5^{m}+0.5^{n}+0.5^{n}$$ but $$0.95^{m+1}+0.95^{m+1}+0.95^{n-1}=1.9(0.95^{m})+0.95^{n-1}\\>0.95^{m}+0.95^3(0.95^{m})+0.95^{n-1}=0.95^{m}+0.95^{m+3}+0.95^{n-1}\\\ge0.95^{m}+0.95^{n+1}+0.95^{n-1}>0.95^{m}+0.95^{n}+0.95^{n}$$

So, while $\sum_{i=1}^{100}0.5^{l_i}$ remains equal to $1$, we can replace $m,n,n$ with $m+1,m+1,n-1$ to improve the chance of survival. This means that the best chance of survival is obtained when the maximum and minimum lengths differ by at most one. The only way to do this is to have 28 sequences of length 6 and 72 sequences of length 7 ($\frac{28}{64}+\frac{72}{128}=1$).

One easy way to implement this is to make the $x$th question asked (remembering to use the modification at the top of this answer):

When the number of the correct door is written in binary, is there a digit 1 in the place that represents $2^{x-1}$?

If the right door is between 37 and 64 inclusive, it will be the only one left after 6 questions. Otherwise, it will require a 7th question. The probability of survival is $0.28(0.95^6)+0.72(0.95^7)\approx70.863\%$, which is optimal as proven above.

Answer 2

By binary search, you can narrow it down in just

$\lceil\log_2100\rceil$, or 7, questions.

You can't do better since every question gives you one bit of information, and asking a question to decide between two sets of doors is always better than guessing between the two.

The question you ask is as follows:

Would you answer "yes" if I were to ask you if the right door is in the list [first half of remaining possible doors]?

It doesn't matter which guard you ask.

So the probability of escape is :

$.95^7$, or about $69.83\%$.

Edit: The above time is wrong (thanks for pointing it out, Matt and durum!); I assumed the worst case scenario, which I should not have done with probability. The real chance with this strategy is better, about $70.8\%$, but it could be improved by another strategy that doesn't cut them evenly.

Edit 2: f'' has proven that this solution is optimal.

Answer 3

Actually, I think the accepted answer is wrong and your chance of survival is actually slightly better at:

70.2984%

using the following strategy

Divide the list into 3 parts, one with 64 numbers, one with 32 number and one with 4 numbers. Ask any guard "If I were to ask you if the right door is in this list of 62 numbers, what would you say?" If he says yes, you discard the other two lists and proceed to cut the list in half every time. If he says no, you throw away the list of 64 and proceed to the list of 32. If it's on that list, you proceed with cutting it in half every time and discard the list of 4. If not, you discard it and follow the same sequence with the list of four. If it is on one of the first two lists (96% chance), you have a 69.8337% chance of surviving. If it is on the third list (4% chance), you have a 81.4506% of surviving. (.04 * 81.4506) + (.96 * 69.8337) = 70.2984% chance of survival.

Answer 4

I love the truth-teller - liar problems and first time attempting to answer on this site. Correct me if I am on the wrong path :)

First of all we must find a question X, which has to have 50% yes, 50% no answer chance which we know. "Are you a real guard? Yes-No?" Answer has 2 possibilities: Yes or No, So we will know if he is telling the truth or not. If he is telling the truth, with the power of n, we can find the number of questions to find the correct door: 2^n. There are 100 possibilites so n must be greater that 7 for a guaranteed correct answer. So we must ask 6 more questions to the guard to find the correct door. 2^7 = 128 but 2^6 = 64, which is not enough for an optimal survival strategy so I pick 7. Now we have got the 0.95 probability of being correct because of the coin toss even if all answers are correct. For survival, it must be 7 times in a row heads, so my formula goes to (0.95)^7 = 0.69833729.... best probability of survival in my opinion

Answer 5

Everybody already stated that which question is to be asked to get right answer from Truthteller or Liar with the question below;

If I were to ask you ____, would you answer yes?

So the second part is the hardest part I believe, so I tried to get a better answer. I divided hundred doors into 64 and 36 ones, then 36 doors into 16 and 20, then 20 doors into 8 and 12, then 12 doors into 8 and 4.

So as a result, I started to ask the question above;

If I were to ask you that the right door is among the first 64 doors, would you answer yes?

So if you got yes answer, it is just $0.95^7$, but you have $64 \ percent$ chance to get yes answer. But to chance to get no is $36 \ percent$. It is not that low. So I divided 36 into different parts as stated above and found the answer below;

$0.95(\frac{64}{100}0.95^6+\frac{36}{100}0.95(\frac{16}{36}0.95^4+\frac{20}{36}0.95(\frac{8}{20}0.95^3+\frac{12}{20}0.95(\frac{8}{12}0.95^3+\frac{4}{12}0.95^2))))=0.70863$

This is how to find the optimum, which is the same answer as f" but simpler to understand :)

Answer 6

Ask a boolean question to any guard to ascertain if they are truth teller or liar. Then: if they are truth teller, ask which door, if they are liar, ask them to tell you a door which contains a monster.