There is a train with 'N' cabins, a monkey is present in one of the cabins initially (which is unknown). Your goal is to catch the monkey, given you can open a cabin every minute and monkey would jump to either the immediate left or right cabin in that time. What is the strategy you use to catch the monkey surely?
N=1 => Trivial case
N=2,3 =>
Open the first cabin twice in case of N=2 and middle cabin twice when N=3. We can surely catch him in at most 2 trials.
First non-trivial case is when N=4 where monkey can just move between any two cabins and hence opening any cabin repeatedly doesn't guarantee that we can catch him, is it possible to find a strategy that works for all N?
Here is one strategy that works:
Check all cabins, one by one, starting from the first. Check the last cabin twice, then start going back through the train the other way. This way, if you missed him the first time around (because you moved forward exactly as he moved backwards and you "passed" one another), he's not going to be able to do the same thing the second time.
This is because of the fact that the monkey always moves from an even cabin to an odd cabin, or vice versa. He never goes from an even cabin to an odd cabin. Thus, if he "slipped by" you on your first pass, then that was only possible because he was in even cabins when you checked odd cabins and the other way around. Checking the last cabin one extra time will "lose a tempo", so that the monkey is forced into a rythm where you check odd cabins when the monkey is in an odd cabin, and you check even cabins when the monkey is in an even cabin. This way, he really can't sneak by you on the second pass through the train.