2
$\begingroup$

Let's say there are doors each with a lock on the integral points ($0$, $\pm1$, $\pm2$, $\cdots$) of the line. You are given a key which can only open a single lock, but you are not told what lock the key is for. Your goal is to find the correct lock and open that door. Initially you are at origin. How can you come up with a strategy to minimize $d/n$ in the worst case, where $d$ is the distance you will be walking in total following that strategy, and $n$ is the distance of the matched door to this given key from origin.

Does anybody here see this problem before? Please give some of your thoughts and solutions.

1 Answers 1

2

I would guess go forward 1 step then back 2 then forward 4 then back 2^3 then forward 2^4 etc. or something like that. To get a nice answer you might need to specify a distribution over n, like a geometric distribution or something with the goal of minimizing the expected number of steps. Or at least an upper bound on n.

It seems like a linear search problem variant. Here is one solution to your original question when posed as a two player zero sum game.

  • 0
    Or ma$y$be a situation $y$ou think is more interesting, or can give simple solutions.2012-01-14