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.
key for opening doors
0
$\begingroup$
number-theory
-
0Compose a strategy for _what_? – 2012-01-29
1 Answers
2
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.
-
0Link to that instead. – 2012-01-29