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?

(In reply to re: interesting question by brianjn)

Yes, I realize it states the restriction, but it does not offer a logical explanation for why he can not move as we do.  In other words, what I am saying is that in visualizing a real-world system of caves for this to work in oviously there must be tunnels connecting each cave to every other cave in order for the searcher to move as stated otherwise in order to move from cave 1 to cave 17 he would have to move thru all the others and thus would catch the enemy on the first day.  But if these tunnels exist then there must be a reason why the enemy can not use them.  Of course a simple explanation would be that these tunnels have some sort of access control that only we are able to circumvent.  Now having said all that I am not trying to invalidate the problem or any solutions offered, I am simply offering an alternative perspective to be considered seeing as that the problem was solved so quickly.

Posted by Daniel on 2008-08-25 22:38:27