Shortest time in which P catches Q

**K Sengupta** · Feb18-09, 11:19 PM

P is hot in pursuit of his enemy Q, who is hiding in one of 17 caves.

The caves form a linear array, and every night Q moves from the cave he is in to one of the caves on either side of it.

P can search two caves each day, with no restrictions on his choice.

For example, if P searches (1, 2), (2, 3), ..., (16, 17), then he is certain to catch Q, though it might take him 16 days.

What is the shortest time in which P can be guaranteed of catching Q?

**davee123** · Feb19-09, 12:50 AM

Well, I can think of a way to get him in 14 days... not sure if it's optimal, though... Hmmm.

DaveE

**Rogerio** · Feb19-09, 02:46 PM

I had found a 14 days solution, too...

Spoiler

[2,4] [2,4] [4,6] [4,6] [6,8] [6,8] [8,10] [8,10] [10,12] [10,12] [12,14] [12,14] [14,16] [14,16]

But then, I realized it could be done in 11 days.

Spoiler

[2,4] [5,7] [8,10] [11,13] [14,16] [17,16] [15,13] [12,10] [9,7] [6,4] [3,1]

**davee123** · Feb19-09, 04:19 PM

Ahhh yes, clever-- take advantage of the fact that if he's in an odd numbered cave on odd days, he has to be in an even numbered cave on even days, and visa versa.

DaveE

**Soca fo so** · Feb26-09, 11:58 AM

I've found a 9 days solution I think...

Spoiler

[2,4] [2,4] [4,6] [6,8] [8,10] [10,12] [12,14] [14,16] [14,16]

Actually looking at it now, it's pretty much the 14 days solution but you don't have to double up on each pair of caves in consecutive days, just the second of the pair.

**Rogerio** · Feb26-09, 12:38 PM

Originally Posted by Soca fo so

I've found a 9 days solution I think...

[2,4] [2,4] [4,6] [6,8] [8,10] [10,12] [12,14] [14,16] [14,16]

Actually looking at it now, it's pretty much the 14 days solution but you don't have to double up on each pair of caves in consecutive days, just the second of the pair.

It is not a solution...
Enemy Q moves:
[5] [6] [5] [4] [5] [4] [5] [4] [5]

**Soca fo so** · Feb26-09, 01:37 PM

Ah yes, damn