There are 13 caves arranged in a circle. There is a thief hiding in one of the caves. Each day the thief can move to any one of the caves that is adjacent to the cave in which he was staying the previous day. And each day, two cops search any two caves of their choice for the thief. So, one cave is searched per cop per day.
The following conditions apply.
- The thief may either move to an adjacent cave or stay in the same cave.
- The cops can check any two caves each day, they do not need to be adjacent.
- The thief only moves to the adjacent cave when the cops are making their rounds.
- If the thief moves from cave X to adjacent cave Y and if one of the cops is going to check on either cave X or cave Y, the thief will be caught.
What is the minimum number of days to guarantee in which the cops can catch the thief?
7 days.
One cop has to search clockwise and the other cop has to search anti clockwise. So, the cops start searching at:
cave 13 and cave 1 on the 1st day
cave 12 and cave 2 on 2nd day
cave 11 and cave 3 on 3rd day
cave 10 and cave 4 on 4th day
cave 9 and cave 5 on 5th day
cave 8 and cave 6 on 6th day
cave 7 on 7th day
The worst case is when the thief stays in cave 7 and does not move.