Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Shortest time in which P catches Q

  1. Feb 18, 2009 #1
    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?
     
  2. jcsd
  3. Feb 18, 2009 #2
    Well, I can think of a way to get him in 14 days... not sure if it's optimal, though... Hmmm.

    DaveE
     
  4. Feb 19, 2009 #3
    I had found a 14 days solution, too...
    [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.
    [2,4] [5,7] [8,10] [11,13] [14,16] [17,16] [15,13] [12,10] [9,7] [6,4] [3,1]
    :smile:
     
  5. Feb 19, 2009 #4
    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
     
  6. Feb 26, 2009 #5
    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.
     
  7. Feb 26, 2009 #6
    It is not a solution...
    Enemy Q moves:
    [5] [6] [5] [4] [5] [4] [5] [4] [5]
     
  8. Feb 26, 2009 #7
    Ah yes, damn :smile:
     
    Last edited: Feb 26, 2009
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Shortest time in which P catches Q
  1. Mind Your p's and q's (Replies: 11)

  2. Shortest time frame (Replies: 5)

Loading...