Friday, September 12, 2008

Lake and Demon

This is a slightly-modified form of one of the most interesting problems from a book I just finished, called How Would You Move Mount Fuji? The book is about using such problems in job interviews, but the context is irrelevant to how clever the problem is. So without further ado:

You're on a boat in the middle of a circular lake. On the outside edge of the lake is a demon who wants to kill you to death. He is bigger than you and has pointy teeth. With poison on them. Death poison. He can't go in the water, so he runs around the edge of the lake, waiting to intercept you when you land.

If you can make it to shore without the demon being right where you land, you'll be okay. You're fast enough over land to run away and escape. But if the demon is right exactly there when you hit shore, you lose. Your wife and kids grieve. Your life insurer goes broke.

Assume the demon and your boat both have a maximum speed, which they can maintain indefinitely. What is the minimum ratio of the speed of your boat to the speed of the demon for you to have an infallible strategy for escape? What is that strategy, and how long does it take you to get to the edge of the lake evading the demon (as a function of the ratio of your speeds, and the ratio of your speed to the size of the lake)?

No comments: