Source

I got this problem from Rustan Leino, who got it from Claude Marché.

I solved it and wrote up my solution.

Problem

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?

Solution
Reveal

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 him the first day when you inspect hole 4. So, he 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 him the second day when you inspect hole 3. So, he 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 him the third day when you inspect hole 2. So, he 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 him the fourth day when you inspect hole 4. So, he must be in hole 2. That night, the hermit moves to an adjacent hole: either 1 or 3.

You don't find him the fifth day when you inspect hole 3. So, he 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 him the sixth day when you inspect hole 2. This contradicts our earlier supposition that you never find him. Thus, the supposition must be wrong, and you do find him within the first six days.