You are hot on the trail of an enemy, who is hiding in one of 17 caves.

The caves form a linear array, and every night your enemy moves from the cave he is in to one of the caves on either side of it.

You can search two caves each day, with no restrictions on your choice. For example, if you search (1, 2), (2, 3), ..., (16, 17), then you are certain to catch him, though it might take you 16 days.

What is the shortest time in which you can be guaranteed of catching your enemy?

Start from one end:

day 1: search 1 & 3
day 2: search 1 & 3

If we didn't catch the enemy, he is obviously not in 1 & 3. He is also not in 2 (if was in 2 on day 1, he would have moved to either 1 or 3 on day 2 and would be caught on day 2). He is not in 4. Because if he was in 4 on day 1 and move to 3, he would be caught on day 2. It is possible he was in 4 on day 1 and moved to 5 on day 2. Basically, on day 2: 1, 2, 3, & 4 are out

day 3: search 5 & 7
day 4: search 5 & 7

Based on the same logic, he is not in 5, 6, 7, & 8.

If this was a 9 cave problem, the enemy would be caught on the fifth day (8 / 2 + 1).

Since this is a 17 cave problem. the enemy can be caught on 9 days (16 / 2 + 1)

Posted by jpy on 2008-09-05 00:48:03