Finding a hermit
Problem: There are five holes arranged in a line. A hermit hides in one of them. Each night, the hermit moves to a different hole, either the neighboring hole on the left or the neighboring hole on the right. Once a day, you get to inspect one hole of your choice. How do you make sure you eventually find the hermit?
Source: Puzzle collection of K. Rustan M. Leino, Microsoft Research
Update (02/01/10): Give a deterministic strategy to find the hermit such that the hermit knows our strategy and would want to escape.
Update (03/01/10):
Solution: Partial solutions provided in comments by Saurabh Agarwal (CSE, IITB 2006-2010) and Giridhar Addepalli (CSE, IITK alumnus and Yahoo! Sr. Software Engineer). Detailed solution posted by me in comments!!
Update (20/12/10):
A general solution for n holes posted by Gaurav Sinha (chera) (CSE IITK 1996 Graduate, Now working at Indian Revenue Service) in comments!
Source: Puzzle collection of K. Rustan M. Leino, Microsoft Research
Update (02/01/10): Give a deterministic strategy to find the hermit such that the hermit knows our strategy and would want to escape.
Update (03/01/10):
Solution: Partial solutions provided in comments by Saurabh Agarwal (CSE, IITB 2006-2010) and Giridhar Addepalli (CSE, IITK alumnus and Yahoo! Sr. Software Engineer). Detailed solution posted by me in comments!!
Update (20/12/10):
A general solution for n holes posted by Gaurav Sinha (chera) (CSE IITK 1996 Graduate, Now working at Indian Revenue Service) in comments!
Check the 3rd hole each day.
ReplyDeleteAssuming that the crab isn't aware of our strategy & his choice of left / right is equal:
there is a 0 probability that he will never cross the 3rd hole
@Shantanu.. we want a deterministic strategy..
ReplyDeleteThe strategy is deterministic :
ReplyDeleteCheck the 3rd hole each day.
Eventually you have to find him since the probability of him crossing the 3rd hole is 1.
@Shantanu..
ReplyDeleteI am sorry.. got my definitions wrong. :( Yes your strategy is deterministic. We want a deterministic strategy to find the hermit given that the hermit knows our strategy and would want to escape.
check in the following order..
ReplyDelete1,2,3,4,5,5,4,3,2,1 and u will catch ur hermit.
pity the hermit tho.. why is he hiding again?
3,2,3,4,3,3,2,3,4
ReplyDeleteshorter:
ReplyDelete2,3,4,3,2,3,4
shorter:
ReplyDelete2,3,4,4,3,2
@saurabh.. nice.. thanx
ReplyDeletecan someone give a proof that it would work? :)
With single monitoring sequence we need to cover all the cases.
ReplyDeleteWe use set I to hold the initial position(s) of hermit.
sequence 2, 2, 3, 4, 4, 3, 2 will guarantee that we find the hermit at some point during the sequence
first 2, 2 will take care of I= {1,2} cases
next 3, 4 will take care of I={3,5} cases.
only case left is I={4} case.
Since all the other initial cases are taken care of by now, we are free to extend the monitoring sequence from now on as we wish just to take care of I={4} case.
Now only position hermit could be in are {1,3}.
Now hermit is to the left of us. To make sure he stays left of us, we monitor 4 again.
From now on it is easy to follow solution.
@Pratik : When r u going to post solution for " Top Card " Puzzle ? :-)
@Giridhar @Saurabh..Thanx a lot.
ReplyDelete@Giridhar.. Actually, as pointed by Saurabh, a 6-length operation will do the job.
Lets prove that 2,3,4,2,3,4 is sufficient and will always give us a solution.
Initially, the hermit could be in either {1,3,5} or {2,4}
If initially the hermit was in {2,4} we can prove that the operation 2,3,4 always finds the hermit.
(Proof: If 2 did not work, the hermit was in 3. So, it would have moved to 3 or 5. If 3 did not work in the second chance, it was at 5. So, it will now move to 4 and will get caught in the third catch)
Now for the case when it begins a place in {1,3,5}. After 3 days, it would go to one in {2,4} and so now a 2,3,4 operation will find the hermit.
Awesome soln. guys!
ReplyDeletehmm i got a slightly longer solution using the same logic (i assumed odd holes first and did 1,2,3,4,5 n then even, etc).
ReplyDeletecomment @ shantanu, pratik - you dont need to reword the problem, the original problem was correct. a deterministic solution is one which catches the crab irrespective of the crabs movements. or rather, formally, for all strategies of the crab, i will still catch him. If the crab's strategy is 121212121212... then Shantanu's strategy will not catch it, and hence it is not deterministic.
it is wrong to assume random movement and choice of L/R to be equal. you are not allowed to assume ANYTHING about the crab's movements, and a similar thought goes with all such problems.
@Ramdas..
ReplyDeleteJust clarifying the definition: Deterministic Strategy is a strategy in which the steps taken by the player depends only on the state of the game. No random parameter is involved. Shantanu's strategy is deterministic as the steps taken by the player (i.e. checking at 3) has no random parameter. For all the states of the game, the operation is the same. Hence, Shantanu's strategy is deterministic.
That is why the change in the statement that "Find a deterministic strategy that always gets the hermit given that hermit knows our strategy"
ReplyDeletearey, completely misunderstood me :P
ReplyDeletehis strategy was deterministic in its moves but probabilistic in its finding the hermit :P
when the question says give a strategy to find the hermit - it implicitly means give a deterministic (ur defn) strategy to find the hermit deterministically (for sure, independent of what his strategy is).
i think answer is :
ReplyDelete3 2 2 3 4 4 3 2 2
@Jitender..
ReplyDeletePlease read the comments of the post.. Your solution seems correct :) But one can get better (smaller) solutions :)
just generalizing the solution given by pratik. if there are n holes,then
ReplyDeletesequence of inspection should be,
Part 1: 2,3,4...,(n-1);
followed by
Part 2: (n-1),(n-2),...2.
if hermit started in an even numbered hole, then hermit will be found in part 1.
otherwise
if hermit started in odd numbered
hole , then hermit will be found in part 2.
Proof: The end holes 1 and n are not checked because, before being caught in these end holes, hermit will be found in hole 2 or hole n-1. in both parts we are traversing from one end to other and parity of our movement is different in part 1 and part 2. Hence hermit will be caught in whichever part our parity matches with that of hermit.
if we follow this generalisation then 234432 should be looked to find the hermite.This also works but why can't we generalise as follows
DeletePart 1: 2,3,4...,(n-1);
followed by
Part 2: 2,3,4...,(n-1).
if we follow this generalisation then 234432 should be looked to find the hermite.This also works but why can't we generalise as follows
DeletePart 1: 2,3,4...,(n-1);
followed by
Part 2: 2,3,4...,(n-1).
@chera.. General solution looks correct to me. In fact, this question was asked in one of the placement tests at IITB
ReplyDeletewhy don't you just go 1,2,3,4,5 to catch the hermit? since the holes it can be hiding in are in a straight line it can't jump from hole 5 to hole 1 (or from 1 to 5) so by the 5th day (even if the hermit knows your strategy) it would be caught since both you and the hermit would be at hole 5. Doesn't that work or am I reading the problem wrong...
ReplyDeleteThat does not work. Initially when you check 1, the hermit might be in 2. And then, before you check 2, it might move to 1. And then just move around from 1 to 2 and 2 to 1 while you go around searching from 2 to 5. Hence, your solution will not work.
ReplyDeletecan it be 1,1,2,3,4?
ReplyDelete@Kiri,
ReplyDelete1,1,2,3,4 does not work.
Suppose initially, the hermit was is hole 3.
Day1: You checked in 1. Fail
Night1: Hermit moved to 2.
Day2: You checked in 1. Fail
Night2: Hermit moved to 1.
Day 3: You checked in 2. Fail.
For the next two nights, hermit keeps oscillating between 1 and 2. You will not be able to catch him.
Hope that helps. Cheers!
I believe 22344 is the shortest possible.
ReplyDeleteI start with 4, you check 2.
DeleteI move to 3. You check 2.
I move to 2. You check 3.
I move to 1. You check 4.
I move to 2. You check 4.
Fail
two times 22344 will work.. what i mean to say is 2234422344.. so, its length is 10...
Deletebetter take 2,3,4,2,3,4.
I also thought the same way :-D
But, after seeing the solution in the posts, i got to know there can be a length 6 solution. :-)
How can we prove this is a optimal solution. By this I mean for general case 2,3,4.....N-1,N-1,.....3,2.
ReplyDelete3 3 4 3 3 2 repeating this sequence again and again one can always catch the hermit
ReplyDelete