99 doors to doom

Logic Level 5

You wake up in a small, locked room of a huge, luxurious 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 behind 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? Give your answer to 3 decimal places.

The answer is 0.7086.

2 solutions

Alex Li
Jun 5, 2015

To determine if a statement $S$ is true or false, you can ask any guard the following question: "If I were to ask you if $S$ is true, would you say yes?" Now, this problem boils down to the number of yes-no questions needed to find the right door out of the $100$ . It is easy to see that, because $2^6<100<2^7$ , you will need $7$ questions to determine definitively the safe door (You can ask questions such as "If I were to ask you if the number of the safe door greater than $50$ , would you say yes?"). If you use this strategy, you will have a $0.95^7=0.698$ probability of survival. However, if you ask fewer than $7$ questions, there will always be at least $2$ doors to choose from, so your probability of survival is at most $0.5$ . Thus, the strategy of definitively determining the correct door is optimal, and $\boxed{0.698}$ is our answer.

Moderator note:

You should explain the line of "However, if you ask fewer than $7$ questions, there will always be at least $2$ doors to choose from" better. It is not immediately apparent that asking 6 conditional questions will not yield a better approach.

Maybe I'm wrong, but I believe you would have a slightly higher chance than if you just assume your binary search will require 7 questions, because remember that for some of them, you will only need 6.

For example, when you have narrowed your search down to 3 doors, there is a 2/3 chance you will need to toss again, and a 1/3 chance you will have the right door, so from there the chance of success is

$P_3 = \frac {1}{3} + \frac{2}{3}\times t$

where t is 0.95, the success rate of a coin toss.

With 7 doors remaining, there is a 3/7 chance of getting to the P value above, and a 4/7 chance of having 4 doors left, which means the chance of success is simply $P_4 = t^2$ . This means that

$P_7 = t\times(\frac {3}{7} \times P_3 + \frac{4}{7}\times P_4)$

Following this reasoning from the bottom to the top, I arrived at

$P_{100} = 0.7086$

Sam Williamson - 5 years, 10 months ago

the solution can be obtained one question earlier by creating a double negative. Don't ask the guard if the correct door is between 51-100. Ask him, instead, what he WOULD say if you WERE to ask him if the correct door is between 51-100. Lets say that the door number is 24.
If the first question was "is the correct door between 51-100" the truth teller would say no, the liar would say yes.
If, however, you instead asked, "If I were to ask you if the correct door were between 51-100, would you say yes?" The truth teller, who knows he would say no if he were to be asked, tells the truth and says no. The liar, who knows he will say yes if he were to be asked, lies and says no.

Dane Sanders - 5 years, 8 months ago

Really nice problem. I used a computer science based approach though.

Here's the optimal strategy:

Step 1: Determine the truthfulness of any ONE guard. Without loss of generality, assume this to be the guard in door 1. We can find his truthfulness by asking him exactly one question. (eg: "Does the sun rise in the east?")

Now we cleverly use this guard to single out the door required by implementing the binary search algorithm on the 100 doors(including door 1).

Step 2: Implement binary search algorithm as mentioned above. Ask the soldier where the door is in each stage and use his response to half your search field in each turn. Binary search wikipedia

It is important to note that the implementation of binary sort takes exactly six question to identify the required door with no ambiguity. In this case it is true no matter where the door is.

Hence, we asked one question in Step 1 and six in Step 2, making a total of seven questions.

In order to survive, the guard must have tossed a head each time a question is asked(seven times). Since each toss is independent, the required probability $P$ is:

$P=(0.95)^{7}\approx 0.6983$

Raghav Vaidyanathan - 6 years ago

How do you determine the door in exactly 6 question? $2^6 = 64 < 100$ .

Calvin Lin Staff - 6 years ago

I wrote a c++ program that found out the number of steps required for each case. That is, it found the number of steps required if the door was 1, 2,3, 4 etc up to 100. All of it came out to be $6$ .

I think we can say this using a heuristic argument too, based on the fact that the number of doors to check halves after each question. But I'm not sure how to go about doing it.

Here is the program if anyone wants to refer to it(it directly gives probability required):

#include <iostream.h> 
#include <conio.h >
#include<math.h>
#define   SIZE  200 

class binSearch
{
float A [ SIZE ] ;
float s ;
int   n ;
public :
binSearch();
void rArray (int );
int   ser (int) ;
} ;

binSearch::binSearch()
    {
    for(int i=0;i<SIZE;A[SIZE]=0,i++);s=0;n=0;
    }

void   binSearch::rArray (int a1 )
{
n=a1;
for (int i=0 ;i<n; i++)
        {A[i] =i+1;}
}

int   binSearch::ser ( int j)
{
int l , u , m,cou=0 ;
s=j;
l   =   0  ; u=(n-1)    ;
while (l<=u)
    {
        m   =   (   l   +   u   )   /   2  ;
    if(l==u)
        {break;}
    else   if (   s <   A [ m  ] )
        u   =   m   -   1  ;
    else
        l   =   m   +   1  ;
    cou++;
    }
return  cou;
}

int main ( )
{
binSearch ob1 ;
clrscr ( ) ;
int n;cin>>n;
ob1.rArray(n);
double p=0;
for(int i=1;i<=n;i++)
    {
    double d=ob1.ser(i);
    p+=pow(0.95,(d+1))/100;
    }
cout<<p;
getch ( ) ;
return 0;
}

Raghav Vaidyanathan - 6 years ago

@Raghav Vaidyanathan – Say the correct door is door 1.
What is the (explicit) series of questions that you will ask, in order to determine that?

How does that change if the correct door is door 100?

Calvin Lin Staff - 6 years ago

@Calvin Lin – 7 questions is wrong.

Let's say the door is 74,

Raghav's algorithm tries to do this:

Is it <50 (no)
Is it <75 (yes)
Is it <62 (no))
Is it <68 (no)
Is it <71 (no)
Is it <73 (no)
Is it <74 (no)

This is 7 steps, but his algorithm doesn't seem to count the last step here. If you don't do that final comparison, then the answer could be 73 or 74.

His algorithm doesn't count the last step because it is actually doing TWO comparisons each time, essentially "is guess correct?", if not "is door < guess". In that case, 6 steps will do, but that's actually 12 questions (+1)

So, you need 8 questions, 1 to find the type of guard, then 7 to find the door.

So, the correct answer is $0.95^8 = 0.663$ , not $0.95^7$ .

Paul Smith - 5 years, 10 months ago

@Paul Smith – With 7 questions, we can generate $2^7 = 128$ different possible answers, and map them to the 100 doors. Alex didn't actually specify an algorithm to state these questions, but it's relatively easy to generate them. They might not be of the form "Is the answer <50", but more like "Is the answer in this list of X numbers", and then based on Yes/No replies we can obtain the actual value.

My concern is that "Why can't we do this with 6 conditional questions?" E.g. If the first question was "Is the answer less than 30" and we obtained the answer Yes, then we could only use 5 more questions after that. So, is there a way to ask 6 conditional questions, to get 100 different answers?

Calvin Lin Staff - 5 years, 10 months ago

@Calvin Lin – You need 7 questions to accurately get down to 1 door for sure, however, you do not have to validify the guard if you ask your questions properly (e.g. "if i were to ask guard 1 (the guard by door 1) if guard 2 would say that guard 3 would say that... that guard 100 would say that the door leading to freedom is between doors" then give the range of the first half of the doors that have not been eliminated yet), you would eliminate half of the doors every time (as if the man says yes, you know that it is NOT in that range, and if he answers no, you know that the door IS in that range). This makes it so that 7 trys are needed, as any fewer decreases your overall chance (i used a computer to graph (0.95^x)/(round up(100/(2^x) ) ) and found the max to be at x = 7) and the probability at that point is 0.698.... (P.S. round up is the same as the ceiling function.)

Kevin McKnight - 5 years, 9 months ago

@Kevin McKnight – In a few situations, 6 trys will work, however, to be certain for any given situation, 7 trys are needed

Kevin McKnight - 5 years, 9 months ago

@Calvin Lin – I understand the feeling: Who said you have to half always? Maybe there is a tricky way... But a yes/no answer gives you one bit information. So you ask this: Is there a way to represent 100 in 6 bits? No.

My much bigger concern is Sam Williamson's comment - and nobody answered that - but that is a different solution, and I think he is right. With a set strategy there is different possibility for each number (door). And if we consider that any number between 1 and 100 can be the right door, so the solution is not exactly 0.95^7 (which I gave, too, of course :))

First Last - 5 years, 8 months ago

@First Last – I forgot to post this with my answer earlier, but I made a python function to solve the problem using the reasoning I mentioned in my answer above.

from math import floor

def doors(n):

    t = 0.95

    if(n == 1):
        return 1

    if(n > 1):
        n1 = floor(n / 2);
        n2 = n - n1;
        return t * ((n1/n)*doors(n1) + (n2/n)*doors(n2));

You can try different values and notice that $doors(128)$ yields the same value as $0.95^7=0.6983$ (as it should). However you would expect that with fewer doors, your odds of success are better, which is why $doors(100)=0.7086$ .

Sam Williamson - 5 years, 6 months ago

@Sam Williamson – I am with you, but nobody else cares :(

First Last - 5 years, 6 months ago

@Sam Williamson – You are absolutely right. The truth about probability is that we need to consider all the plausible cases, and in this problem it's 18/25 probability that we take 7 questions, and 7/25 for 6 questions. And, your python code is also correct.

I needed to solve it, couldn't do it in time, so had to post it here: http://puzzling.stackexchange.com/q/26123/1766

Anubhav Balodhi - 5 years, 4 months ago

@Anubhav Balodhi – Thanks. I have updated the answer to 0.7086.

Could you make a note on SE that you obtained the problem from here? Thanks.

Calvin Lin Staff - 5 years, 4 months ago

@Calvin Lin – Yes, I did :-)

Anubhav Balodhi - 5 years, 3 months ago

It all depends on your guesses. I could theoretically determine the answer in two questions: If your coin, once flipped, lands on heads, will a monster devour me? ...and... Is the safe door numbered X?

You determine the truth or liar in the first question, and luck can aid you in guessing the correct door in your first guess. Logic and probability would dictate that there is a 1/100 chance of guessing the correct door the first time, thereby giving me a 90.25% chance of survival, should I randomly select the proper door.

Before you say that this Is not the 'optimal' strategy, isn't the optimal strategy one that gives you the castle in the least number of questions, thereby reducing the chances of demise? By that logic, my method is the most optimal strategy, though not by statistic and probability equations.

Regardless, based on the question, you have no probability of survival. A liar, based on basic human psychology, can choose when to lie and when not to lie. You have not stated in the question that liars always lie, therefore, a liar may be capable of telling the truth. There is no way to determine who is a truth teller and who is a liar based on one or two questions, since the guard on the other side is a human. Any of the liars may lead you astray in order to see you devoured by a monster.

The question is inherently flawed, so the probability is a 0.00% chance of survival, with a myriad of questions, unless you randomly open the door and survive, thereby giving you a 100% chance of survival, with no questions.

Eddie Spagnoli - 5 years, 8 months ago

I agree that there are some flaws in the description and could be better made, but it can be inferred from the question that the liars have to lie. Also, he wants you to find the probability of the optimal generic strategy. What I mean by this is that the strategy must be one that will work for any door and for any guy (for truth-tellers as well as liars). After all, ideally, you do not even need to ask a question. Best case scenario is that you just pick a door and it is the one door that leads to freedom, making it 100% chance of freedom in this scenario. He just wants a strategy that works for all scenarios (a generic one), with the probability coming in with the flip of the coin.

Kevin McKnight - 5 years, 8 months ago

Bhashwar Ghosh
Feb 23, 2017

Ask any one of the guard 7 questions, and the question number 'i' should be Question i) lf I asked you that " Is the 'i'th digit of the correct door number written in binary system zero?", then what would had you said ? As the max possible digit in binary system would be 7(that of 100 in decimal system), these many question would suffice and probability of your survival would be $0.95^7$ . Yes/No question only gives 2 bits of information, so its easily understood as to why asking such questions ( involving binary system) gives optimal number of questions to fetch required information. Suppose if we asked only $n<7$ questions, then we would had only got the information of first n digits of binary form of the required door number. And successfully guessing other 7-n digits would have a probability of $0.5^{7-n}$ and total probability would have been lesser for survival.

99 doors to doom

The answer is 0.7086.

2 solutions

Moderator note:

0 pending reports