3
$\begingroup$

This is an extension of the puzzle The Minotaur's Labyrinth which is inspired by the comments from histocrat.

You are trapped (again) in a chamber at the center of the minotaur's labyrinth. There are $N$ tunnels, $m$ of which lead to safety; the remaining tunnels only lead back to the chamber. Each tunnel is of a different length, taking $h_i$ hours to travel. Each time you return to the chamber, the room shifts so that you can only choose tunnels at random. However, this time you find the distribution of tunnel length inscribed on the wall. You still don't know the length of any particular tunnel, but you know the distribution of lengths.

You have 24 hours until the Minotaur wakes up. If you are already in a safe tunnel when he wakes up, you will escape safely.


Case 1 Suppose there are 10 tunnels such that $$h_i = \begin{cases} i, & i = 1, 2, \cdots 9 \\ 100, & i = 10 \end{cases}$$ and $2$ tunnels lead to safety.

  1. What is the optimal strategy you should use?
  2. Using the optimal strategy, what is the expected time it will take you to escape?
  3. Using the optimal strategy, what is the probability that you will escape?

Case 2 Suppose there are 10 tunnels such that $$h_i = 2^i$$ and $2$ tunnels lead to safety.

  1. What is the optimal strategy you should use?
  2. Using the optimal strategy, what is the expected time it will take you to escape?
  3. Using the optimal strategy, what is the probability that you will escape?

The strategy with the best probability of survival for case 2 will be accepted.

Using a computer (simulation) to answer questions 2 and 3 is allowed.


Some Clarifications

  • A priori, each tunnel has an equal chance of being "safe"
  • You only know that the tunnel you are in is "safe" once you have traveled to the end of it and realize that you have escaped the labyrinth.
  • When you return to the chamber, the room shifts so that you have no knowledge even of which tunnel you just traveled.
  • I admit, I'm unsure of how one would demonstrate "optimality" here. For now, I'm mostly interested in maximizing probability of survival. The current score to beat is 30.50% by ffao.
$\endgroup$
  • $\begingroup$ How many tunnels are safe in those cases? $\endgroup$ – ffao May 11 '17 at 2:50
  • $\begingroup$ When you say the distribution, do you mean the proportions between the times it takes for you to go through the tunnels or the exact time? $\endgroup$ – boboquack May 11 '17 at 3:13
  • $\begingroup$ I mean exact times. And duh, big oversight on my part. Updating now. $\endgroup$ – knrumsey - Reinstate Monica May 11 '17 at 3:22
  • $\begingroup$ At the start, does every tunnel have the same chance of being an escape tunnel? $\endgroup$ – humn May 11 '17 at 3:43
  • 1
    $\begingroup$ @BigAgnes I got all my answers, Thanks. I will let you know if I have more later. $\endgroup$ – Oray May 11 '17 at 12:18
3
$\begingroup$

The first observation is that our optimal strategy has to consist of, every time we enter a tunnel, determining a cutoff distance d at which we will turn around and come back.

For Case 1, since we have a tunnel that is much bigger than the others (tunnel with length 100), we would expect the optimal strategy to avoid taking this tunnel whenever possible to allow for more exploration, turning at 9 most of the time. Indeed, let's denote by t how much time we have left before the Minotaur arrives, then this is the optimal strategy:

t=20, didn't go through any tunnels: turn at 9
t=21, went through tunnel with size 1: turn at 9
t=21, went through tunnel with size 3: turn at 9
t=22, didn't go through any tunnels: turn at 9
t=22, went through tunnel with size 1: turn at 9
t=22, went through tunnel with size 2: turn at 9
t=23, went through tunnel with size 1: turn at 9
t=24, didn't go through any tunnels: turn at 9

This gives a winning probability of 59.45%. Assuming you do win, you're expected to take 21.10 hours to do it.

For Case 2, there are several large tunnels and several small tunnels. It makes sense to come back frequently to try for one of the small ones; the large ones consume too much time. And this is what we see in the optimal strategy, as it turns back quite early to try to explore smaller tunnels:

t=14, didn't go through any tunnels: turn at 2
t=14, went through tunnel with size 4: turn at 2
t=14, went through tunnel with size 8: turn at 2
t=16, didn't go through any tunnels: turn at 2
t=16, went through tunnel with size 4: turn at 2
t=16, went through tunnel with size 8: turn at 2
t=18, didn't go through any tunnels: turn at 4
t=18, went through tunnel with size 4: turn at 2
t=20, didn't go through any tunnels: turn at 4
t=20, went through tunnel with size 4: turn at 2
t=22, didn't go through any tunnels: turn at 4
t=24, didn't go through any tunnels: turn at 4

The winning probability of this strategy is 30.50%. Assuming you do win, you're expected to take 572.22 hours.

(This answer earlier solved the arguably more interesting case in which $h_i = 2^{i-1}$ instead of $h_i=2^i$. See the edit history for the strategy in that case.)

In case it isn't obvious by this point, no, I did not generate these tables by hand :)

The c++ code I used to determine these strategies can be found here: https://pastebin.com/vFU9tc2D

$\endgroup$
  • $\begingroup$ What is the expected time it takes you to escape for each of these cases? $\endgroup$ – knrumsey - Reinstate Monica May 11 '17 at 5:08
  • $\begingroup$ @BigAgnes I added the times assuming you do escape (so not counting the cases in which the Minotaur gets you). Assuming my program is right, of course... $\endgroup$ – ffao May 11 '17 at 5:32
  • $\begingroup$ Thanks! Very interesting that in the second case the time is so long. Inflated by those potentially long tunnels! $\endgroup$ – knrumsey - Reinstate Monica May 11 '17 at 5:36
  • $\begingroup$ how do you not know taking h=100 or i=10 leads you the safety exit? why do you go back? $\endgroup$ – Oray May 11 '17 at 11:30
  • $\begingroup$ @ffao, darn late night puzzle posting. I agree $2^{i-1 }$ would have made things slightly more interesting. $\endgroup$ – knrumsey - Reinstate Monica May 11 '17 at 12:10
1
$\begingroup$

Partial :
CASE 1 :

It takes on average $\frac{\sum h_i}{10}$ hours to try one tunnel, and the chance to find the a correct tunnel is $\frac 2{10}$ so on average you will need to try $\frac {10}2$ tunnels. $\frac{\sum h_i}{10}$ X $\frac {10}2$ = $\frac{\sum h_i}2$.
If I understand correctly, the last tunnel takes 100 hours, so the most efficient thing to do is turn back after 9 hours. so 18 hours will be consumed.

$\sum h_i=1+2+3+4+5+6+7+8+9+18=63$

So on average it will take $\frac{63}2 = 31.5$ hours to find the exit.

I am not sure how to calculate the probability to get out in time but I suppose it is something like :
You need to take into account that your are safe past 24h if in a good tunnel so : $\frac{63}{10} * \frac 2{10} = 1.26$ -> average time of 1 path divided by the chance of being in a good path gives the average time extension.
And the final probability would be something like :
Probability that $24 + 1.26 \gtrsim 31.5$

Important note. If m = 1 and the 10th tunnel is the correct one.... tough luck.

CASE 2 :

It takes on average $\frac{\sum h_i}{10}$ hours to try one tunnel, and the chance to find the a correct tunnel is $\frac 2{10}$ so on average you will need to try $\frac {10}2$ tunnels. $\frac{\sum h_i}{10}$ X $\frac {10}2$ = $\frac{\sum h_i}2$.

$\sum h_i=1+4+8+16+32+64+128+256+512+1024=2045$

So on average it will take $\frac{2045}2 = 1022.5$ hours to find the exit.

I am not sure how to calculate the probability to get out in time but I suppose it is something like :
You need to take into account that your are safe past 24h if in a good tunnel so : $\frac{2045}{10} * \frac 2{10} = 204.5$ -> average time of 1 path divided by the chance of being in a good path gives the average time extension.
And the final probability would be something like :
Probability that $24 + 204.5 \gtrsim 1022.5$

EDIT
I forgot to optimize. When the path takes too long, it is best to turn back and try another path to raise your chances slightly. Returning after 8 hours is the only one that makes sense because returning at 16 hours would not be fast enough to try a new path.

$\endgroup$
  • $\begingroup$ Can you run some simulations with your proposed strategy and give the average escape time and probability of survival? $\endgroup$ – knrumsey - Reinstate Monica May 11 '17 at 5:11
  • $\begingroup$ @BigAgnes I'm afraid I would need to make a program to get any more precise data. Sorry. $\endgroup$ – stack reader May 11 '17 at 5:42
  • $\begingroup$ In case 1, I believe your initial calculation is correct, but when you turn back after 9 hours for the 10th tunnel, won't this change the assumption that 5 tunnels must be traveled on average to escape? $\endgroup$ – knrumsey - Reinstate Monica May 11 '17 at 12:35

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.