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?
Let us denote the individual and his enemy by D and E. Then D is guaranteed to catch E in at most fourteen days.
First day : D checks the caves 2 and 4.
Second Day: D checks caves 2 and 4 once again. If E was on caves 1 or 3 on first day, then he must be in cave 2 or cave 4. This is a contradiction. Hence, E cannot be located in caves 1 to 4 inclusively on the second day.
Third day: D checks caves 4 and 6.
Fourth day: D checks caves 4 and 6. If E is not on either of the caves, then he cannot be in any of the caves 1 to 6.
Fifth day & sixth day: D checks caves 6 and 8.
Seventh day and eighth day: D checks caves 8 and 10.
Ninth day and tenth day: D checks caves 10 and 12.
Eleventh day and twelfth day: D checks caves 12 and 14
Thirteenth day and fourteenth day: D checks caves 14 and 16.
Thus, in each of the (2n-1)th and 2n th day, D will check for caves 2n and 2(n+1), and if E is in neither, then by similar arguments, it follows that E cannot be in caves 1, 2, …., 2(n+1).
However, we know that at any given point of time E must be located at one of the caves 1 to 16.
Thus, for n = 7, we note that on 13th day or 14th day E must be located either in cave 14 or cave 16, if none of D's earlier checks had failed to pinpoint E.
Consequently, D will catch E in at least fourteen days.
Edited on December 26, 2008, 12:50 pm
Solution
