Posted tagged ‘chase’

Chasing the terrorist

December 4, 2008

(Presented by Wojciech Mostowski in IPA herfstdagen 08)

There are two characters that move along a line: a terrorist and a policeman. The line has only discrete positions, this is, it is possible to count the possible positions on the line. However there are infinitely many positions to both sides of the line.

The terrorist is very predictable. At each move, he advances one position on the line. The initial position and direction is unknown, but he never changes the direction.

The policeman can jump between any position in the line, but he can only move at the same time the terrorist moves.

The question is: is there any strategy  for the policeman to move along the line that guarantees that he will catch the terrorist in a finite number of steps? Catching the terrorist means being on the same position as him.