Consider five holes in a line. One of them is occupied by a fox. Each night, the fox moves to a neighboring hole, either to the left or to the right. Each morning, you get to inspect a hole of your choice. What strategy would ensure that the fox is eventually caught?

From a puzzle collection by K Rustan M Leino at Microsoft Research.

Let holes be numbered 1 thru 5. Inspecting the holes in any of the following sequences suffices:

  2, 3, 4, 2, 3, 4

  2, 3, 4, 4, 3, 2

  4, 3, 2, 2, 3, 4

  4, 3, 2, 4, 3, 2

Explanation for sequence 2, 3, 4, 2, 3, 4: Let F denote the set of holes where the fox might be hiding. On any morning, the fox is either in an even numbered hole or an odd numbered hole. So on the first morning, either F = {1, 3, 5} or F = {2, 4}. If F = {2, 4}, then the following sequence of inspections suffices to catch the fox: 2, 3, 4. However, if the fox was not caught, then F must have equalled {1, 3, 5} on the first morning, so F must equal {2, 4} on the fourth morning. Therefore, repeating the sequence 2, 3, 4 from the fourth day onwards would suffice to catch the fox.

Another explanation to convince us that the sequence 2, 3, 4, 2, 3, 4 suffices to catch the fox: Let F denote the set of holes where the fox might be hiding. Initially, F = {1, 2, 3, 4, 5}. If the fox is not in hole 2, it must move so that F = {2, 3, 4, 5}. If the fox is not in hole 3, it must move so that to F = {1, 3, 4, 5}. If the fox is not in hole 4, it must move so that F = {2, 4}. If the fox is not in hole 2, it must move so that F = {3, 5}. If the fox is not in hole 3, it must move so that F = {4}.

Is there a strategy for n holes in general? Can you prove that your strategy is optimal?