13 Caves And A Thief Puzzle

Problem:

There are 13 caves arranged in a circle. There is a thief  in one of the caves. Each day the the thief can move to any one of adjacent cave or can stay in smae cave in which he was staying the previous day. And each day, cops are allowed to enter any two caves of their choice.

What is the minimum number of days to guarantee in which cops can catch the thief?

13-caves-and-a-thief-puzzle-150x150

Note:
Thief may or may not move to adjacent cave.
Cops can check any two caves, not necessarily be adjacent.

Solution:

Lets assume the thief is in cave C1 and going clockwise and cops start searching from cave C13 and C12 on your first day.
Cave C13 and C11 on second day,
C13 and C10 on third day and so on till C13 and C1 on 12th day.
So basically the aim is to check C13 everyday so that if thief tries to go anti clockwise you immediately catch it and if goes clockwise cops will catch him in maximum 12 days (this include the case where he remains in Cave C1).

Answer is 12.

24 Thoughts on “13 Caves And A Thief Puzzle

  1. In the given soln, if initially on the first day the theif was in c11, and jumps to c12 the next day he can’t be catched right..??

  2. Lets say thief is in C1 and he’s not moving from C1. Cops started searching from (C13, C12), (C13, C11) …etc. On 11th Day Cops will search (C13.C2) after this search, thief can start moving from C1 to C2. Next Day i.e., 12th Day Cops start searching in C13, C1 but the thief is in C2 now. So, he can escape.

    Solution: The problem statement should be made very clear. COPS can search in Day Light time and Thief Can move in Day Light Time. Otherwise it’s possible for the thief to escape. As usually thief operate in nights ;-)

  3. vivekjoshi on October 24, 2013 at 9:34 am said:

    Your solution is wrong
    My solution for the given problem is that assuming thief in cave C1 and cops on C2 AND C3 both are moving in clockwise direction, so this way at max thief will be caught on 12th day, your question should be like at max. how much time will police take to catch the thief

  4. Anonymous on October 24, 2013 at 4:51 pm said:

    This is wrong. Assume thief is in C2 all the time. Cops search C13, C12|C13 C11…|C13 C3. Next Day Thief goes to C3 and cops search C13, C2. Question should have a condition that thief can not come back to cave already he was in once visited.

  5. Ved Verma on December 24, 2013 at 6:49 am said:

    suppose cops were in c12 and c13 ob first day while theif was in c11.
    on 2nd day cops are in c13 and c11 but thief moved to c12 and remain there for next 12 days. total days took is 13.
    please correct me if i am wrong

  6. Actually, If they can start from adjacent caves (For instance, C10 and C09), they would definitely catch the thief in 6 days.

  7. Manish K on June 1, 2014 at 11:51 pm said:

    Never. Solution is crooked. Are you copy-pasting from other sites?
    When You move from C2 to C1 thief will move from C1 to C2.
    Then he again get back to C1 in second round and keep repeating it for every round.
    In short You can never catch thief.

  8. Kapil Deep on September 5, 2014 at 6:28 pm said:

    Shyam you are right with half of your approach but just think if for instance the thief start following clockwise (for instance) and when the cops which are moving clockwise n anticlockwise are about to clear each other he changes his direction n start moving opposite than again they need maximum 12 days

  9. Mark the cell as 1 to 13 assume that thief is in 7th Cell and cop started checking from cell in order as mentioned

    1 and 2
    13 and 3
    12 and 4 in such a case in worst case it will take 7 days to catch the thief even if thief is moving in either direction or not moving at all. The condition is both thief and cops are not moving togather or there is only one way one can move from one cave to another.

  10. data insufficient

  11. Rupinder on January 7, 2015 at 12:06 pm said:

    I think we are assuming that the Thief knows that there are cops searching the caves and that they can search 2 caves in a day.

    It is not mentioned in the puzzle that the Thief is aware of this and hence there is no incentive for the Thief to move caves.

    The cops should search 2 caves in sequence and at minimum on the 7th Day they would catch the Thief.

  12. Shan Sreenivas on January 14, 2015 at 11:01 am said:

    The Answer 12 is not correct. we can find the theif within 7 days.
    Lets assume the thief is in cave C6 and going clockwise and cops start searching from cave C1 and C13 on your first day.
    Cave C2 and C12 on second day,
    C3 and C11 on third day and so on till C6 and C8 on 6th day. On the 7th day the theif is caught

  13. Solution is wrong for sure. If thief doesn’t follow pattern. Like I said in my first comment. If thief moves C5-C6 and cop moves C6-C5. And again, thief C(i)-C(i+1) and cop C(i+1)-C(i) everytime. Having a cop in C13 all the time, will never solve this problem.

  14. Manas Tiwari on February 25, 2015 at 12:47 pm said:

    if the cop checks c8 the first day and c7 the next day and the thief moves from c7 to c8 .. He’ll never be caught … and if their correct then the minimum days will b 7 .. HOW? .. cops start checking from c7 and c6 and then c8 and c5 .. and so on .. and to correct their solution cops will have to check 3 caves in a day .. keeping a cop at c13 fixed and moving other 2 cops anticlockwise checking adjacent caves each day … THINK OVER EVERYONE PLEASE!!

  15. Prateek Gupta on March 3, 2015 at 2:34 pm said:

    find like c1-c2->c2-c3->c3-c4… as thief can stay in same or move to adjacent thus max of 12 days required..

  16. Mesar ali on July 26, 2015 at 2:57 pm said:

    12 days required as given
    C1- c13
    C1-c2
    C13-c12
    C2-c3
    C12-c11
    C3-c4
    C11-c10
    C4-c5
    C10-c9
    C5-c6
    C9-c8
    C6-c7

    • See how the thief can escape from your solution. Denote the thief by T. T1 means the thief stays in c1. Initially the thief stays in c2.

      C1- c13 — T2
      C1-c2 — T3
      C13-c12 — T2
      C2-c3 — T1
      C12-c11 — T1
      C3-c4 — T1
      C11-c10 — T1
      C4-c5 — T1
      C10-c9 — T1
      C5-c6 — T1
      C9-c8 — T1
      C6-c7 — T1

  17. If the cops can start from adjacent caves, they will definitely catch the thief in 6 days.

    let us assume @first day, thief is in c1, and cops started from c7 & c8, in worst case thief doesn’t change his location for next 5 days, and cops will start from c7 & c8, and they ll continue in their path (c7 in anti-clockwise & c8 in clockwise).

  18. shashank on December 21, 2015 at 12:42 pm said:

    Say the thief is in c11, a/c to the solution the cop 1st checks in c12 and c13 on 1st day so what if on second day thief goes back to c12 from c11 , the cop will never be able to find the thief.
    Correct me if i am wrong.

  19. Alekh on July 7, 2016 at 3:57 pm said:

    there is no guarantee of cops catching the thief. this problem minimum guarantee is when thief dies.

  20. There is no guarantee to catch the thief.
    Each day he has 3 available caves to be at, and the cops can only cover 2. So there is always the possibility of him choosing one the cops don’t check.

    Even if you had him surrounded at C2 with cops at C1 and C3. If the next day they enter C2, he that will leave C1 or C3 empty, and he could have moved there. If they don’t check C2, he could just stay there.

  21. Meet Patel on April 28, 2017 at 11:54 am said:

    The question is flawed. No matter how you try, there will be a chance for the thief to escape every time. Even for an indefinite no. of moves

  22. Tolokoban on March 16, 2020 at 4:22 pm said:

    The problem becomes more interesting if the thief has to move everyday.
    He can only go to one of the two adjacent caves, but never stay in the same.

    With this restriction, you can use the Zugzwang principle to solve it.

Leave a Reply to ganesh Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation