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 Slowly, slowly, catchee... by ed bottemiller)

From what I understand of your search pattern:

Day 1: Search caves 8 and 10.
Day 2: Search caves 8 and 10.
Day 3: Search caves 7 and 11.
...
Day 9: Search caves 1 and 17.

Suppose your enemy began (Night 0) in cave 6.
Day 1 search finds no enemy.
Night 1: Your enemy moves to cave 7.
Day 2 search finds no enemy.
Night 2: Your enemy moves to the already searched cave 8.
Day 3 search find no enemy.... (And he has evaded your search pattern!)...

Posted by Dej Mar on 2008-08-25 13:20:26