Imagine you are standing next to a long fence, extending as far as you can see in both directions. You want to cross the fence and you know that somewhere it has a hole you can go through. But, you don't know whether the hole is to your right or left, or how far away it is. You want a strategy for finding the hole that does well using a competitive ratio measure.

Let's model this problem as follows: you are initially located at the origin on the real line. The hole is at some (positive or negative) integer coordinate n. You can move left or right at cost equal to the distance moved, and the game continues until you reach n. You then look at the ratio of your cost to |n| (n is the optimal off-line cost since it is the distance you would have travelled if you had known where the hole was). Design a deterministic algorithm whose competitive ratio is at most 9.