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.
We first make the observation that, for any integer $r > 0$, there are exactly $4r$ possible pairs $(A, B)$ such that $|A| + |B| = r.$ Here's why. There are four such pairs where one of them is zero: $(0, r), (0, -r), (r, 0), (-r, 0).$ Then, for each $1 \leq i \leq r-1,$ there are four such pairs where $|A| = i:$ $(i, r-i), (-i, r-i), (i, i-r), (-i, i-r).$ Thus, there are a total of $4r$ such pairs.
At each time interval $n,$ make a guess $(A_n, B_n)$ for what the values of $(A, B)$ are. Then, ask about location $A_n + n B_n$. If your guess was right, i.e., if $A_n = A$ and $B_n = B,$ then you'll find the spy.
Make the guesses as follows. For time interval $0,$ guess $(0, 0).$ Then, for the next four time intervals, guess the various values of $(A, B)$ satisfying $|A| + |B| = 1.$ Then, for the next eight intervals, guess the various values of $(A, B)$ satisfying $|A| + |B| = 2.$ And so on.
After time interval $0,$ you will have guessed the only pair $(A, B)$ satisfying $|A| + |B| = 0.$ After time interval $(4 \sum_{i=1}^s i) = 2s(s+1),$ you will have guessed all possible pairs $(A, B)$ satisfying $|A| + |B| \leq s.$ Thus, after time interval $2(|A|+|B|)(|A|+|B|+1),$ you will have found the spy.