Problem of the Week 1164

Stop the Battleship

A battleship 4 units long is traveling along the real line. It is moving with constant speed M units per second, M an unknown integer, but we do not know whether it is moving left or right. It starts with its left end at some location N, again an unknown integer.

At each second you can fire a shot at some integer point; if the shot strikes the battleship, the process ends and you have succeeded.

Describe a strategy that guarantees success in finite time.

Source: MSRI Puzzle Column by J. Buhler and E. Berlekamp, who indicate that this might have been used as an interview question at a hedge fund.

© Copyright 2013 Stan Wagon. Reproduced with permission.

[View the solution]