techsuns

 Consider five holes in a line. One of them is occupied by a fox. Each night, the fox moves to a neighboring hole, either to the left or to the right. Each morning, you get to inspect a hole of your choice. What strategy would ensure that the fox is eventually caught?

@Kranthi: So the worst case of catching the fox is 5 for this example.............. since we go by randomness............. Is there efficient way to do this.........
kp

given holes 1 2 3 4 5

check hole 1 first day : if fox in 1 caught 

if in 2, next day either to 1 or 3 so simply check 2 : if it had gone to 1 next day on checking 2 caught. That's day 3.  if it had gone to 3 and comes back to 2 again caught.

So on day three if fox not caught we know fox is in  4 5. (since from 3 it would move to 2 or 4)

So on 4th day check 3rd hole if fox comes back it  otherwise in 4 or 5 . If in 4 next day to 3 or 5 so check 3rd hole on 5th day again. if 3 then  otherwise sure 5 so check 4 next day. 6 days 

The answer is as follows -

234234-

Initially fox can be in either {1,2,3,4,5}. Assume in the first day fox can be in either {2,4}- then strategy to catch the fox is 2,3,4. But if we are not able to catch then which means initially fox was in {1,3,5}. So on 2nd day fox will be in {2,4}, on third day {1,3,5,}, on fourh day again on {2,4}. Hence, we have to repeat the same sequence - 2,3,4 again to catch the fox.

@ravu Good question