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?

ok maybe this is a dumb question, but if we are able to move from any cave to any other cave at will then would that not imply that our enemy could do the same?  I see nothing in the problem desription that could explain this.  So pending the resolution of this question I am going to answer another question.  If he is able to move as freely as we are then obviously there is no way to guarentee to catch him, so if we choose 2 caves at random to search each day and he moves to a random cave each day, what is the expected number of searches to catch him?  well the odds of catching him each day is 2/17, thus the expected number of searches is 8.5.  Now the question I leave open is if this is better than the expected number of searches for already submitted search methods?

Posted by Daniel on 2008-08-25 21:15:49