Leaping frog algorithm

Question

I need your help with a riddle, I need to find the best algorithm to catch a frog, The frog is on the Natural numbers, it begins at point L, each time it goes K Leaps right (means if it was at point X, now it is at point x+k), we don't know what is L and each time that we try to catch it and miss, it goes k steps more... (We also don't know what is k), How can I find the best algorithm to always catch it?

I though I can just go and jump for eternity but I guess it's not a good answer... Thanks for helping...

Answer 1

The position at instant $n$ is $\;x(n)=L+nk$.

If there is no known upper bound on $k$ and $L$ you may simply try all the values of $(L,K)$ in $\mathbb{N}\times \mathbb{N}$ starting at the origin and with the constraints $L+k=C$ with $C$ increasing once the diagonal was handled i.e. try the couples (for $n=0,1,2,3,\cdots$) :

$$(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3),(1,3)\cdots$$

(the path being the same than in the Cantor proof of equivalence between $\mathbb{Q}$ and $\mathbb{N}$)

Of course at instant $n$ you'll have to search at $x(n)=L+nk$.

Answer 2

The frog is on one of a countable set of possible trajectories, indexed by the pair $(L,k)$, where $L$ denotes its starting point and $k$ its "speed." For each possibility, you can compute where it will be on the $n$th attempt to catch it (namely $L+(n-1)k$). So simply list the possible trajectories, and on the $n$th attempt go to where the $n$th trajectory predicts the frog to be.