This is a nice example of using some maths to solve a puzzle from the mindyourdecisions youtube channel (screencaptures from the video).
How to Avoid The Troll: A Puzzle
In these situations it’s best to look at the extreme case first so you get some idea of the problem. If you are feeling particularly pessimistic you could assume that the troll is always going to be there. Therefore you would head to the top of the barrier each time. This situation is represented below:
The Pessimistic Solution:
Another basic strategy would be the optimistic strategy. Basically head in a straight line hoping that the troll is not there. If it’s not, then the journey is only 2km. If it is then you have to make a lengthy detour. This situation is shown below:
The Optimistic Solution:
The expected value was worked out here by doing 0.5 x (2) + 0.5 x (2 + root 2) = 2.71.
The question is now, is there a better strategy than either of these? An obvious possibility is heading for the point halfway along where the barrier might be. This would make a triangle of base 1 and height 1/2. This has a hypotenuse of root (5/4). In the best case scenario we would then have a total distance of 2 x root (5/4). In the worst case scenario we would have a total distance of root(5/4) + 1/2 + root 2. We find the expected value by multiply both by 0.5 and adding. This gives 2.63 (2 dp). But can we do any better? Yes – by using some algebra and then optimising to find a minimum.
The Optimisation Solution:
To minimise this function, we need to differentiate and find when the gradient is equal to zero, or draw a graph and look for the minimum. Now, hopefully you can remember how to differentiate polynomials, so here I’ve used Wolfram Alpha to solve it for us. Wolfram Alpha is incredibly powerful -and also very easy to use. Here is what I entered:
and here is the output:
So, when we head for a point exactly 1/(2 root 2) up the potential barrier, we minimise the distance travelled to around 2.62 miles.
So, there we go, we have saved 0.21 miles from our most pessimistic model, and 0.01 miles from our best guess model of heading for the midpoint. Not a huge difference – but nevertheless we’ll save ourselves a few seconds!
This is a good example of how an exploration could progress – once you get to the end you could then look at changing the question slightly, perhaps the troll is only 1/3 of the distance across? Maybe the troll appears only 1/3 of the time? Could you even generalise the results for when the troll is y distance away or appears z percent of the time?