I-Spy

Solution

The key idea is that although \(A\) and \(B\) are unknown, the pair \[ (A,B) \] is just an integer pair. The set of all integer pairs is countable, so we can arrange them in a list: \[ (A_0,B_0),\ (A_1,B_1),\ (A_2,B_2),\ \dots \] in such a way that every possible integer pair appears somewhere in the list. Now use time \(n\) to test the \(n\)-th candidate pair in that list. If at time \(n\) the candidate pair is \[ (A_n,B_n), \] then ask whether the spy is at location \[ A_n+nB_n. \] Why does this work? Suppose the spy’s true starting point and velocity are actually \[ (A,B). \] Since our list contains every integer pair, there is some time \(n_0\) for which \[ (A_{n_0},B_{n_0})=(A,B). \] At that time, our guess is \[ A_{n_0}+n_0B_{n_0}=A+n_0B, \] which is exactly the spy’s true location at time \(n_0\). So at time \(n_0\), we catch the spy. That gives a complete algorithm: At time \(n\), take the \(n\)-th integer pair in some fixed enumeration of all pairs \((a,b)\in \mathbb{Z}^2\), and query the location \[ a+nb. \] Because every possible \((A,B)\) appears somewhere in the enumeration, this strategy is guaranteed to succeed eventually. An intuitive way to think about it is that each possible spy-behaviour corresponds to one straight-line motion rule \[ x(t)=A+tB. \] Since there are countably many such rules, you can test them one by one. When you finally test the correct rule at the matching time, your query lands exactly on the spy. A concise final version is: List all integer pairs \((a,b)\) as \[ (a_0,b_0),(a_1,b_1),(a_2,b_2),\dots \] At time \(n\), ask whether the spy is at \[ a_n+nb_n. \] If the true motion is \(A+tB\), then for some \(n_0\), \[ (a_{n_0},b_{n_0})=(A,B), \] so at time \(n_0\) you ask about \[ A+n_0B, \] which is exactly the spy’s location. Hence the spy is eventually found.