Gurmeet.Net
Gurmeet.Net
Puzzles
Puzzles

Fox in a Hole

Puzzle

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?

Source

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

Solution

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}.

Followup

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

Previous Puzzle: Cake Cutting

Mary baked a rectangular cake. Merlin secretly carved out a small rectangular piece, ate it and vanished! The remaining cake has to be split evenly between Mary's two kids. How could this be done with only one cut through the cake?

Next Puzzle: Cube Cutting

Imagine a 3x3x3 wooden cube. How many cuts do we need to break it into twenty-seven 1x1x1 cubes? A cut may go through multiple wooden pieces.

13 Aug 2009
© Copyright 2008—2017, Gurmeet Manku.