Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
1  
Do the liars always lie? – jhabbott Feb 5 at 14:15
3  
Do the guards know which door is the right one? – Cyrus Feb 5 at 15:33
1  
And yes, all guards know about the 'Door to Freedom'... – ABcDexter Feb 5 at 15:43
1  
Good thing there's 100 guards instead of 2, else I'd headbutt the first guard and wrestle-down the second and have plenty of gear for monster killing. – Joshua Feb 5 at 22:05
3  
@ABcDexter Drat, if I'm allowed to ask such questions, I think the existence of a third response means I can form questions to the effect of "Which of these three sets of doors" instead of "Which of these two?" Should probably add that to the constraints, something to the effect of "If a guard can't answer your question with yes or no, he kills you for trying to game the system." – Ninety-Three Feb 5 at 22:20
up vote 13 down vote accepted

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.

share|improve this answer
    
Thanks for your edit on my edit... sloppy of me to leave out the "and"! – ErikE Feb 6 at 2:01
1  
The probability shown is correct for the scheme. And though the explanation as to why this scheme is optimal is extremely hard to follow, it does appear to be correct as well.. – Paul Sinclair Feb 6 at 5:23
    
@f'' That is the correct method to solve it, considering all the plausible cases. And yes, the probability of survival is also better (according to your final answer.) – ABcDexter Feb 6 at 9:21
    
very good explanation. Thanks @f" – Oray Feb 6 at 20:53

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.

share|improve this answer
5  
@WaKai It lies in the "What would you say if I were to ask you" part. Let's say you ask a liar "Are you a liar?", he would clearly say "No". But if you ask "What would you say if I were to ask you if you are a liar?" The answer to this is "yes" because the answer to "are you a liar" is "No" and he has to lie about that. So he lies about the answer of the orignal question so he will always tell the truth with this wording – Ivo Beckers Feb 5 at 9:46
3  
@IvoBeckers I'm not sure the phrasing of the question is quite right: A liar's answer to "What would you say if I were to ask you if you are a liar?" could be "Blancmange" (because the correct answer is "Yes" and thus "Blancmange" is a lie). Unfortunately, "Blancmange" would also be a valid response to the full question whether it is the right door or not. I think that "Would you answer YES to the question..." would be a suitable prefix. – TripeHound Feb 5 at 11:01
1  
@TripeHound I think that, given you can only ask the guards yes/no questions, it's safe to assume they can only answer with a yes or no. – Doc Feb 5 at 15:22
2  
Nice answer. Note that you will ask at most 7 questions. The average should be around 6.72 so the probability of surviving is about 0.7084393. – durum Feb 5 at 16:28
3  
There's an 18/25 chance you need 7 questions, and 7/25 you need 6, for a probability of about 0.7086 – Matt Feb 5 at 21:12

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.

share|improve this answer
1  
I think it should better than that, 0.95^4 = 0.8145062, so the final result is 70.2649% – durum Feb 5 at 19:58
    
@durum You're right, I messed up. If it is he last set, you will only ask 4 questions, not 5, which is what I originally thought. But I am getting 70.2984 – Kevin Feb 5 at 20:03
    
Now this cannot be improved with the strategies -well variations of one- posted here... I wonder if there is a method even better... – durum Feb 5 at 20:06
    
@Kevin Thanks for a better answer/strategy. I'll cross-check and update the accepted answer accordingly. – ABcDexter Feb 5 at 20:10

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

share|improve this answer
3  
You can save one question by XORing all your questions with "are you a truth-teller". – 2012rcampion Feb 5 at 8:35

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 :)

share|improve this answer
    
Interesting, let me cross-check. – ABcDexter Feb 9 at 9:55

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.

share|improve this answer
3  
you can't ask which door contains the monster coz they can answer only yes or no – manshu Feb 5 at 14:39
    
@manshu You are right. If we ask a liar whether (s)he's a liar, then answer would be "No", from both of them. – ABcDexter Feb 5 at 20:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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