Question

Phoebe plans to eat out for lunch every day for two weeks, choosing from a row of 9 waterfront restaurants. She promises her brother Will that, if he picks one restaurant per day and manages to find her there, she will buy his meal for him. She intends to move venues daily but, to make Will's life a little easier, she will always move just one restaurant to the left or to the right, choosing her direction at random (unless at either end of the row, when her next move is forced). Will is not aware at which restaurants Phoebe has eaten. Either use a diagram to illustrate Will's strategy for finding Phoebe within the given two weeks and thus guaranteeing him a free lunch or else show that no such strategy exists.

Answer 1

Phoebe's motion is a "random walk" with a "reflecting barrier." It works out that the expected number of days for Pheobe to end up N positions from her start at one end of the row is N^2. Even if Will adopts the strategy of always eating at the middle restaurant, it may take Phoebe 16 or more days to finally get there if she starts at the end. 16 days is beyond the 2-week time period.

If will goes hunting for Phoebe, there always exists the possibility that she next eats at the restaurant he just left. Will cannot know, for example, that Phoebe will always eat at even numbered restaurants on even days. (She may eat at odd restaurants on those days.) Consequently, he has no basis for narrowing his search.

While I believe eating at the middle restaurant, thus narrowing the possible range of motion of Phoebe, is Will's best strategy, it is certainly not guaranteed to find Phoebe.