I got this problem from Rustan Leino, who got it from Claude Marché.
I solved it and wrote up my solution.
There are five holes arranged in a line. A hermit hides in one of them. Each night, the hermit moves to a different hole, either the neighboring hole on the left or the neighboring hole on the right. Once a day, you get to inspect one hole of your choice. How do you make sure you eventually find the hermit?
Assign the holes the numbers 1 through 5, from left to right. Inspect the holes each day in the following order: 4, 3, 2, 4, 3, 2.
Suppose this strategy doesn't work, and you don't find the hermit within the first six days. Then, we can reason as follows.
You don't find them the first day when you inspect hole 4. So, they must be in hole 1, 2, 3, or 5. That night, the hermit moves to an adjacent hole: either 1, 2, 3, or 4.
You don't find them the second day when you inspect hole 3. So, they must be in hole 1, 2, or 4. That night, the hermit moves to an adjacent hole: either 1, 2, 3, or 5.
You don't find them the third day when you inspect hole 2. So, they must be in hole 1, 3, or 5. That night, the hermit moves to an adjacent hole: either 2 or 4.
You don't find them the fourth day when you inspect hole 4. So, they must be in hole 2. That night, the hermit moves to an adjacent hole: either 1 or 3.
You don't find them the fifth day when you inspect hole 3. So, they must be in hole 1. That night, the hermit moves to the only possible adjacent hole: 2.
So, it's impossible that you don't find them the sixth day when you inspect hole 2. This contradicts our earlier supposition that you never find them. Thus, the supposition must be wrong, and you do find them within the first six days.