# The Minotaur's Labyrinth

You are trapped in a chamber in the center of the Minotaur's Labyrinth. There are $\mathbf{N}$ tunnels, $\mathbf{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.

1. What is the expected amount of time it will take you to escape?
2. You have 24 hours until the Minotaur wakes up. If there are 10 tunnels, such that $h_i = i$ (for $i$ = 1,2,...10) and two of the tunnels lead to safety do you believe you will escape in time?
• Can I turn around once it becomes clear I'm in a tunnel I'd rather not follow to the end? If I know the distribution of tunnel lengths and some are more than twice the lengths of others, that could be a useful strategy, which complicates the math. If the tunnels are [100,1], I'll want to follow a tunnel for an hour, then backtrack if it turns out it's the long one, then repeat until I've followed the short one. For [3,1], I'd want to backtrack after an hour if I've already followed the long tunnel once and know it doesn't lead out. – histocrat Dec 17 '15 at 2:42
• Let's assume you know nothing about these tunnels. – knrumsey Dec 17 '15 at 22:04
• "Knowing nothing" is actually a problematic concept when talking about unbounded integers, though. I can't assign equal probability to all possible distributions of tunnel lengths and still have the sum of all probabilities converge to 1. But if my prior involves shorter tunnel lengths being more likely than longer ones, I might still be able to strategically turn around in some cases. – histocrat Dec 17 '15 at 22:16
• It's not problematic. You can assume the tunnels have finite length, and there are a finite number of tunnels. See the answer given by f'', it assumes no additional knowledge of tunnel length distribution. Let's assume the Minotaur doesn't want to help you optimize your strategy. Although I do agree, what you suggest could make for an interesting alteration to this puzzle... – knrumsey Dec 18 '15 at 23:59
• Sorry, I wasn't clear. What I mean is, for example, what is the probability that there is at least one tunnel of length less than a billion hours? Saying "the tunnels have finite length" doesn't completely describe the "probability density function" that a minotaur victim would have. To put it another way, it's impossible to pick a random number and not have some numbers be more likely than others. At some point, larger numbers have to start getting less likely. But then the possibility of strategy emerges. – histocrat Dec 19 '15 at 3:24

## 1 Answer

1. You spend an expected $\frac{\sum h_i}N$ hours each time you travel a tunnel, and you have to travel an average of $\frac Nm$ tunnels to escape. The product is $\frac{\sum h_i}m$ hours total.
2. $\sum h_i=55$ and $m=2$, so the expected amount of time to escape is $\frac{55}{2}=27.5$ hours.
• What is the probability of escaping within 24 hrs? – jez Dec 16 '15 at 2:08
• @jez It appears to be 58.5%. The expected value is receiving a significant contribution from the possibility of very long times (e.g. 2.1% probability of still being stuck after 100 hours). – f'' Dec 16 '15 at 2:45
• Did you take into account that the minotaur is released into the chamber (I'm assuming) and if you're already in an escape tunnel, you still escape? For example, after 22 hours you are back in the chamber and choose the 8-hour long tunnel, which happens to be an escape tunnel. You escape after a total of 30 hours. – user3294068 Dec 16 '15 at 17:08