hard | strategy |

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

Here is a detailed solution with images

And here is a short solution:

Since integer 2-tuples $(x,y)$ are countable, there exists a function $f:N \rightarrow N*N$ such that $f$ covers all integer 2-tuples.

Let $f(n)=(f_1(n),f_2(n))$. The algorithm will be to check for location $f1(n) + n\cdot f_2(n)$ at time instant $n$.

Given $A$ and $B$, there exists $n_0$ such that $f(n_0)=(f_1(n_0),f_2(n_0))=(A,B)$, and thus at time instant $n_0$ we will be checking for location $f_1(n_0)+n_0 \cdot f_2(n_0)$ which is $= A+ B \cdot n_0$ - the actual location of the spy.