| 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 are countable, there exists a function such that covers all integer 2-tuples.
Let . The algorithm will be to check for location at time instant .
Given and , there exists such that , and thus at time instant we will be checking for location which is - the actual location of the spy.