You are standing on the middle of a East-West street. A row of closed doors in front of you, and you have a key on hand which can only open one specific door. Compose a strategy so that X/N value is smallest under the worst situation. X is the distance you covered when arriving at the correct door. N is the distance between the door and the original point.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Your problem is known as the cow-path problem. The answer is an example of an online algorithm. The best $X/N$ is known as the competitive ratio. The competitive ratio in your case is~$9$ for deterministic algorithms, and $4.6$ for randomized algorithms.
See Wikipedia for references.