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?
I agree with DejMar that my interpretation and reasoning were faulty. The problem probably means that we search units in DAYLIGHT (I was thinking of each "day" as 24 hours, so that our moves would be continuous, so that the enemy would not be moving into one just as we left it.) Assuming that there are some hours between our searches and the enemy's moving, this won't do.
I looked at the initial solutions by Dej Mar and K. Sangupta, who both suggest 14 days. In either case, it seems to me, at the end of the 14th day we would EITHER have captured the enemy, OR we would know which cave he was in -- so he could be captured on the 15th day (e.g. if he was in 17 all along, then moved to 16 after we left it on day 14). Wouldn't this mean that the capture was guaranteed by the 15th day, assuming the specs?
I hope there is some clever lower solution, since reducing the obvious 16 day search (aka brute-force) using rolling neighbor pairs by only one day (or two?) does not seem very exciting. (I guess that by "linear" the problem means that the caves are "in a row" and that the enemy cannot move between 1 and 17, or otherwise than by +/- 1) Where's Alladin now? If I were "hot on the trail" I would think searching two caves a day was rather leisurely: just frag 'em all!
14 or 15?
