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?
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.
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..??
Thats the point he will nayways move in the coming days so within 12 days he will be cuaght.
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
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
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.
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
Actually, If they can start from adjacent caves (For instance, C10 and C09), they would definitely catch the thief in 6 days.
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.
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
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.
data insufficient
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.
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
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.
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!!
find like c1-c2->c2-c3->c3-c4… as thief can stay in same or move to adjacent thus max of 12 days required..
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
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).
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.
there is no guarantee of cops catching the thief. this problem minimum guarantee is when thief dies.
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.
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
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.