While going on a walk with your monkey, you encounter a long (though finite) row of poles. The poles are so high that you cannot see the top of any of them. Suddenly, your monkey escapes and jumps to the top of one of the poles. You don’t know which one.

The only thing you can do is throw rocks at the poles. If the rock hits at the precise pole your monkey is sitting on, he will jump back to your arms and you could both go home to eat ice cream. However, if you miss, and the rock hits any other pole, then the monkey will jump from the pole he is sitting on to a pole just next to it. So the monkey has two options for where to jump, unless it is at the end of the line of poles.

Find a deterministic tactic that will ensure your success in getting your monkey back and going home to eat your ice cream.

Solution: Starting with the left-most pole, hit the poles one by one, from left to right, until you hit the right-most pole. If you haven’t got the monkey by this time, start with the right-most pole and hit the poles one by one, from right to left, until you hit the left-most pole. You will surely have caught your monkey at this point.

Explanation:  Let us enumerate the poles by the numbers 1, ..., n from left to right. At the first stage you throw rocks at the poles one by one, in increasing order from left to right, from 1 to n.

Case 1:  Consider that before you start the monkey is on a pole with an odd number. The key to solving this case is to consider the distance (D) between the pole where the monkey is and the pole you hit. If D = 0, you have the monkey. In this case the distance D starts as a positive even number (unless the monkey is on pole 1) and ends as a negative number when you reach pole n (if you did not catch him). Also, at each step the value of D either decreases by 2 (if the monkey jumped to the left) or remains the same (if the monkey jumped to the right). As you hit successive poles 1, …, n from the left-most pole to the right, D, which starts as an even number, must go through 0 at some point.  So you would catch the monkey before you reach pole n.

Case 2: Now consider that before you start the monkey is on a pole with an even number. For this case, let’s look at the number of the pole on which the monkey is (K). Every time you throw a rock, the monkey can jump to the left or right. So at each step K changes from odd to even and vice versa. That’s called a change in parity. When you go from left to right the parity changes n times, which is equal to the number of poles in the row and identical to the number of the right-most pole. 

If n is even, then K, which starts an even number, will change parity (from even to odd or vice versa) an even number of times, and the monkey will end on a pole with an even number. On the other hand, if n is odd, then K will change parity an odd number of times, and the monkey will end on a pole with an odd number. In each of these two cases, let’s call the number of the pole on which the monkey ends as “final K.” Therefore, if the monkey starts on an even-numbered pole, then final K and the right-most pole (n) will always have the same parity: either both are even numbers or both are odd numbers.

If we now enumerate the poles from right to left (reverse the numbering), then the rightmost pole (which was pole n in the original enumeration) and the pole that the monkey is on (final K in original previous enumeration) will still have the same parity. But in this reverse enumeration, pole n is now pole 1, which is an odd number. And because this pole is an odd number, then the pole that the monkey is on, final K, must also be odd. This is exactly the same case as we had in Case 1, the monkey starts on an odd-numbered pole, and you will surely catch him before you reach the left-most poll, if you throw rocks on the poles one by one, from right to left.