Catching the spy on a number line

Question

A spy is somewhere on the integer number line. At time 0 the spy is at integer A; at each time step the spy moves B units to the right (B may be negative or zero), so at time t the spy is at A + Bt. Both A and B are fixed integers unknown to you.

At each time t = 0, 1, 2, ..., you may name one location and ask "is the spy there now?" and you are told yes or no.

Devise a strategy that is guaranteed to find the spy eventually, whatever A and B are.

Accepted Answer

Make a list containing every pair of integers (A, B) exactly once. At time t, take the t-th pair on the list, (At, Bt), and ask whether the spy is at At + Bt × t. When the list reaches the true pair, the question hits. Why every pair can be listed. The pairs of integers are countable: order them by the size of A + B, and within each size in some fixed order. There are finitely many pairs of each size (for size s there are 4s of them, and one for size 0), so every pair appears at a finite position in the list. For instance: (0, 0); then (1, 0), (0, 1), (minus 1, 0), (0, minus 1); then the eigh…

Catching the spy on a number line

Your answer

Discussion

Learn the concepts

Related questions