Find Minimum number of days to guarantee to catch the thief
There are 13 caves arranged in a circle. There is a thief hiding in one of the caves. Each day the the thief can move to any one of of the caves that is adjacent to the cave in which he was staying the previous day. And each day, you are allowed to enter any two caves of your choice.
What is the minimum number of days to guarantee in which you can catch the thief?
- Thief may or may not move to adjacent cave.
- You can check any two caves, not necessarily be adjacent.
- If thief and you exchange your caves, you will surely cross at some point, and you can catch the thief immediately.
Lets assume the thief is in cave C1 and going clockwise and you 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 idea is to check C13 everyday so that if thief tries to go anti clockwise you immediately catch it and if goes clockwise you will catch him in maximum 12 days(including the case where he remains in Cave C1).