## November 26, 2008

### 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 maximum number of days in which you can
catch the thief?

Secret Squïrrel said...

The way the question is worded it is possible for the thief to never be caught.

iamgr8 said...

Simple one..

4 Days max..
and minimum 1 day..

Anonymous said...

i was ready to give a answer and then tried proving it out on paper and now i agree with secret squirrel.... possible to never catch him.......(good shot squirrel)

kartik said...

secret squirrel can u explain plz

Gauss said...

The thief can always be caught.Numbering the caves 1,2,3,...,13;let the thief be in the cave,say,i.Now if the we start searching for the thief in the following process:Today we search jth and j+1th.Tomorrow j+2,j+3th.
By this process we gain over the thief by at least 1 cave/day.
The time taken to catch the thief will be at most 12 days.

Secret Squïrrel said...

Gauss' solution only works if the thief is not permitted to enter either of the caves that you checked that day.

Let's say that the thief is in cave 13 and you choose to check 1 & 2 on Day 1. Next day the thief moves into cave 1 and you check caves 3 & 4.

This continues until Day 11 where the thief is in cave 10 and you check caves 8 & 9. Now by Gauss' reasoning, on Day 12 the thief moves into cave 11 and you check caves 10 and 11 thus catching him. However, the thief could simply move the other way into cave 9 which you have already checked so you will bypass him.

Nonetheless, Gauss' solution is a good one and is perhaps the one sought by the puzzle-setter, but the wording needs to be tightened up a bit.

Anonymous said...

Ya you're right

Anonymous said...

The bounds were wrong;

But, did you realize that the thief would only increase the length of the ordeal;but,he is certain to be caught.
The thing is Gauss didn't see the mentioned case was possible in calculating his estimate for the extremum.

My Love said...

Hey.The person who gave the solution is exactly right friends.The explanation goes in this way:

Instead of thinking in a circular way.If the caves are arranged in straight way.This is similar to running race.If one person is running ahead(one step).And the other person is running with an increased speed(2steps)he will certainly overcome the 1st person at some particular stage.And the puzzle is almost similar to this.So "THE POLICE WILL CERTAINELY CATCH THE THIEF AS HE IS MOVING WITH GREATER SPEED(2 STEPS).
--Kumar.T.Anand.

Secret Squïrrel said...

But the caves aren't straight - they are arranged in a circle and it is entirely permissable for the thief to reverse his direction.

The way the question is worded, when you catch up to him, the thief simply needs to move into a cave that was checked the previous day. That way, unless you change your strategy and check the same cave, it is entirely possible that he won't get caught. Ever.

Try it for yourself - you follow your procedure of checking the caves in sequential pairs. At some point you catch up to the thief.

Lets say that the thief is in cave 7 and you check 5 & 6. Now, next day, the thief moves into cave 6 and you check 7 & 8. See? - you've missed him.

Gauss said...

Yes you are right.

Evan said...

There is no maximum! If you're unlucky enough, you may never catch the theif.

BOO!

My Love said...

Hey Secret Squirrel,
What you are saying is absurd. If you are in cave8 and cave9, and the thief is in cave10. As long as you are in cave9, thief cant come in, and if you moved to cave10 and he moved to cave9, definitely there is an intersection of two lines(I mean the thief and the cop). Thats all. The problem will be unsolved if there is no intersection. But there will be an intersection. And therefore the problem is solved.

Ruizxymx said...

Hey Secret Squirrel, What you are saying is absurd. If you are in cave8 and cave9, and the thief is in cave10. As long as you are in cave9, thief cant come in, and if you moved to cave10 and he moved to cave9, definitely there is an intersection of two lines(I mean the thief and the cop). Thats all. The problem will be unsolved if there is no intersection. But there will be an intersection. And therefore the problem is solved.