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?

You can catch your enemy in 14 days.

1st and 2nd day: search caves 2 and 4 (*16 and 14).
3rd and 4th day: search caves 4 and 6 (*14 and 12).
5th and 6th day: search caves 6 and 8 (*12 and 10).
7th and 8th day: search caves 8 and 10 (*10 and 8).
9th and 10th day: search caves 10 and 12 (*8 and 6).
11th and 12th day: search caves 12 and 14 (*6 and 4).
13th and 14th day: search caves 14 and 16 (*4 and 2).

As your enemy moves to an adjacent cave each night, this search pattern will guarantee he will be found in one of the searched caves during the day. 

An alternate search pattern, where each cave is only searched twice which also guarantees discovering your enemy is the following:

1st day: search caves 2 and 4 (*16 and 14).
2nd day: search caves 2 and 5 (*16 and 13).
3rd day: search caves 3 and 6 (*15 and 12).
4th day: search caves 4 and 7 (*14 and 11).
5th day: search caves 5 and 8 (*13 and 10).
6th day: search caves 6 and 9 (*12 and 9).
7th day: search caves 7 and 10 (*11 and 8).
8th day: search caves 8 and 11 (*10 and 7).
9th day: search caves 9 and 12 (*9 and 6).
10th day: search caves 10 and 13 (*8 and 5).
11th day: search caves 11 and 14 (*7 and 4).
12th day: search caves 12 and 15 (*6 and 3).
13th day: search caves 13 and 16 (*5 and 2).
14th day: search caves 14 and 16 (*4 and 2).

*As the caves are in a linear array, one can begin toward either end of the array and search toward the other end.

Edited on August 25, 2008, 10:28 pm

Posted by Dej Mar on 2008-08-25 11:45:59