Problem of the Week 1075

Desperately Seeking Alice

Bob is at the origin, (0, 0), and looking for Alice, who is somewhere inside a disk of radius 2 centered at the origin. Bob can see Alice if he is within distance 1 of her. Bob can take steps in any direction of length exactly 1 and after each step (also at the starting position; but not while he is moving from point to point) he learns if he is closer or farther from Alice than he was at the point he just left.

Find a strategy for Bob that uses no more than five steps to find Alice.

Note. "Closer" means "strictly closer," and "farther" means "not closer," i.e., "farther or the same."

The harder general problem uses a disk of radius D. Can you devise an efficient strategy for Bob in that case?

If Bob's strategy causes him to visit all or almost all of the disk, then the number of steps is quadratic in D. Do it in an asymptotically linear number of steps. Make the coefficent as small as possible. The best known is that it can be done in asymptotically D steps.

Source: Puzzle #21 from The Puzzle Toad, where the problem posed was to find a solution that works in, asymptotically, 3/2 D steps. Solvers there found a solution that is asymptotic to D. In general, finding an optimal strategy for fixed small D might be very difficult. Perhaps the case D = 3 is worth pursuing? The fact that the radius 2 case can be solved in only five steps is due to Michael Wodzak (Viterbo University).

6 March 2007