Some animals are especially evasive, and the cunning fox is definitely near the top of that list. In the dark woods there is a row of 5 holes, one of which contains a fox which moves either to its left or right everyday. Given that you can check one hole everyday, can you design a strategy such that you will definitely catch the fox? Of course you should try to make this strategy find the fox in the least amount of time possible, and it should catch this sneaky animal regardless of whatever it does. Below this photo of Fantastic Mr. Fox, I have put my take on this problem.
Back to the basics, let’s try and work this out for less than 5 holes. What would you do if there was 1 hole? Just investigate that one hole, the fox has to be there. So what about 2? First you have to check one of the holes (you have to start somewhere), and if it is not in that hole, you know it is in the other one, so the next day it has no option but to move back to the hole you checked first. So the strategy would be to check one of the holes twice in a row. If we say that the holes are 1 and 2, the strategy could be 1, 1.
Let’s move onto 3 holes now. I think a sensible first move would be to check the middle hole, after which if we don’t meet our fox we know that it is in one of the two adjacent holes, and has to move back to the middle. Therefore a strategy for this could be 2, 2.
Now with 4 holes, we can start with hole 2 and then go to hole 3. To understand why this is a good start, let’s classify the fox’s starting position as either even or odd. If it is even, it’s either starting in hole 2 or 4. If it starts in 2, we have caught it, and if it starts in 4, it has to move to 3, and therefore the second day we catch it. So these two moves guarantee the capture given that the fox starts on an even hole. If it started on an odd hole, it will currently now be on an odd hole, as two days have passed and each day the fox switches from odd to even (or vice versa). So let’s check 3, as the fox has to be on either 3 or 1. And similar to before, but flipped on the symmetry of the holes, if the fox is at 1, it has to move back to 2, so we then check that hole. To sum up the strategy, we first take care of the case of the even starting position, and then odd, giving us the strategy 2, 3, 3, 2.
And we now arrive at our intended 5 holes. To keep our trend going, we’ll start with hole 2. If the fox was initially at an even position, after checking hole 2 it is either caught, or is at 3 or 5 (having moved from 4). So next turn we’ll check hole 3 to make sure that it doesn’t lurk off to the other side. Now, given that it started in an even position, we have either caught it or it had gone from 4 to 5, and now it has no option but to go to 4, and so we simply check this hole. The sequence 2, 3, 4 can therefore find the fox if it started in an even hole. But what about odd? Now after this sequence of 3 days, if the fox started in an odd position, it has to be in an even position. But we already found the strategy for catching the fox if it starts on an even hole. So let’s just repeat that. What do we get? This is our strategy which guarantee catching the fox: 2, 3, 4, 2, 3, 4.
Another way to approach this problem would be to write a program which finds all possible permutations so the fox’s routes and matches these to a solution. In this answer, I have purposely only found one solution, and suggest you try and find all the possibilities, and perhaps try and extrapolate some trends by comparing the solutions for different numbers of holes. How do the solutions compare when there is even vs. odd total number of holes? Can you generalize this problem?