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?

This is probably not minimal, but let's see.  I assume the enemy could choose a cave you have previously searched, so long as it is adjacent to his previous cave. Also that the enemy could return to a previous hiding spot, if adjacent. Also assume that if you find a cave empty you have no way to determine whether it was occupied the day before.

Start with (8,10). Repeat (8,10) on second night. Catch or exclude 8, 9, 10. Then (7,11) thru (1,17) until caught (i.e. each day you eliminate two more cells.  Hence maximum of ninth day.

 

Posted by ed bottemiller on 2008-08-25 13:00:19