Catching a Spy


I got this problem from Rustan Leino, who got it from Radu Grigore.

I solved it and wrote up my solution.


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.

Solution     Reveal