The problem of Tom and Jerry

Note that, had we known which half of the real axis (positive or negative) Jerry is hiding, the problem would be trivial; Tom just needs to run along that direction until he catches Jerry. This would give us $\alpha=1$ . The difficulty here is that we do not know this information, thus we have to search on both sides of the line.

Call each consecutive visits of Tom to origin a round . Similar to the Binary Search , it can be shown that an optimal strategy is to run exponentially increasing lengths alternatingly on each side at each round, i.e., Tom runs a distance of $2\times 2^{n-1}$ units at round $n, n \geq 1$ alternatingly on each side of the origin. Suppose Jerry is hiding at a distance $J$ from the origin. Then, there must exist two consecutive powers of $2$ such that $2^{k} < J \leq 2^{k+1}$ Hence, at the worst case, the total distance run by Tom before he catches Jerry is given by $T= 2\sum_{n=1}^{k+2}2^{n-1} + J \leq 8\times 2^{k}+J$ Hence, $\frac{T}{J} \leq 8\frac{2^k}{J} +1 \leq 9. \hspace{10pt} \blacksquare$

Note

(1) The above algorithm is an example of Online algorithm and the method of analysis is known as Competitive Analysis .

(2) If we had allowed randomized strategy too, the expected distance Tom must run could be reduced to $7 J$ . Do you see why?

(3) What if instead of the $x$ -axis only, Jerry could also hide somewhere on the $y$ -axis too. What would be the minimum $\alpha$ in that case?

(4) What if Jerry could hide anywhere on a $d$ -dimensional integer lattice ?