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?

© Copyright 2008—2017, Gurmeet Manku.