0

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?

dronz3r
  • 144
  • Are the cabins placed in a circle ? Otherwise , I do not understand the case $N=3$ because in this case, the monkey must be in the middle cabin within at most $2$ minutes. – Peter Oct 23 '19 at 09:29
  • @peter No, they are not in a circle. Yes, opening the middle one repeatedly is easier strategy in the case of N=3. – dronz3r Oct 23 '19 at 10:05
  • See https://puzzling.stackexchange.com/questions/455/why-does-this-solution-guarantee-that-the-prince-knocks-on-the-right-door-to-fin – Bram28 Oct 27 '19 at 13:18

1 Answers1

2

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.

Arthur
  • 199,419

  • Check all cabins, one by one, starting from the first. If the monkey starts in an odd-numbered cabin, you're going to catch him.

     – dronz3r Oct 23 '19 at 10:26
  • @Sireesh Yes, what about it? Do you not believe me? – Arthur Oct 23 '19 at 10:29
  • sorry,am new to this platform, edited the comment. Let's say N=4, we search 1,2,3,4. But monkey can follow 2,1,2,1. – dronz3r Oct 23 '19 at 10:39
  • @Sireesh Yes, it can. In this case, id didn't start in an odd-numbered cabin, so we didn't catch him. However, is is now in an odd-numbered cabin, meaning we can catch him if we start from $1$ again. In fact, let me make an easier recipe to follow, where one doesn't have to think at all to follow it correctly. – Arthur Oct 23 '19 at 10:46
  • Understood. Thanks a lot! – dronz3r Oct 23 '19 at 11:03