Home > Logic
| Catching your enemy (Posted on 2008-08-25) |
 |
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?
|
|
Submitted by pcbouhid
|
|
Rating: 2.3333 (3 votes)
|
|
|
Solution:
|
(Hide)
|
14 days.
First 2 days, just check caves 2 and 4. Next two days, check caves 4 and 6. Keep going like that.
On day 1, you either find him or rules out caves 2 and 4.
After that, on day 2n you either find him or rule out all caves less than 2n+3, and on day 2n+1 you can rule out all caves less than 2n+5, except cave 2n+3.
Thus, on day 13 you have either caught him or eliminated all caves except for caves 15 and 17. So by checking caves 14 and 16 on day 14 you will catch him.
|
Comments: (
You must be logged in to post comments.)
|
|
Please log in:
Forums (0)
Newest Problems
Random Problem
FAQ |
About This Site
Site Statistics
New Comments (16)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On
Chatterbox:
|
