Catching a spy

[I got this problem from Radu Grigore.]

A spy is located on a one-dimensional line. At time 0, the spy is at location A. With each time interval, the spy moves B units to the right (if B is negative, the spy is moving left). A and B are fixed integers, but they are unknown to you. You are to catch the spy. The means by which you can attempt to do that is: at each time interval (starting at time 0), you can choose a location on the line and ask whether or not the spy is currently at that location. That is, you will ask a question like “Is the spy currently at location 27?” and you will get a yes/no answer. Devise an algorithm that will eventually find the spy.

©2020-2023 K.R.M. Leino - Split Template by One Page Love