# Puzzle: Give an algorithm for finding a frog that jumps along the number line

You are playing a game, your goal in this game is to catch a frog that's leaping between natural numbers.

At first, the frog is found at the number $a \in \mathbb N$ which is not known to you. Each turn, you take a guess at where the frog is found.

If you are right - you win.

If you are wrong - the frog leaps $b \in \mathbb N$ numbers to the right. Meaning, if you got the first guess wrong, the frog is now at $a+b$. If you get the guess wrong again, it's now at $a+2b$.

Neither $a$ or $b$ are known to you. All you know is that they are natural numbers.

Propose an algorithm that will find the frog in a finite number of steps, regardless of what $a$ and $b$ are.

Additional challenge: Same question, but now $a,b \in \mathbb Z$.

• This sounds like a (Martin Gardner?) problem I have heard before, only that one involved bombing a submarine instead of findind a frog. – Mike Pierce Dec 30 '14 at 20:04
• I'm an eternal pacifist... – Oria Gruber Dec 30 '14 at 20:05
• Leave the frogs alone. Experiment on yourselves. – Doug Spoonwood Dec 30 '14 at 20:07
• If you know the $b$, the algorithm is easy. Firstly say that the frog is at the 1st position. If you're wrong then say that it's at $2+b$. Again if you're wrong then say that it's at $3+2\cdot b$. Each time when you're wrong say that the frog is at $(k+1)+k\cdot b$. You will surely win in mostly $a$ steps, so the algorithm's complexity is O(a). – Vladimir Fomenko Dec 30 '14 at 20:07
• You do not know $b$. But regardless I would like to hear your proposed solution for that case. Even though it is not relevant to our question. – Oria Gruber Dec 30 '14 at 20:08

For fixed $a$ and $b$, after $m$ steps, the frog will be at $a + mb$ if you haven't guessed right yet. The set of pairs $(a, b) \in \mathbb{N}\times \mathbb{N}$ is countable, so you can enumerate it, say as $(a_0, b_0), (a_1, b_1), \ldots$. Now guess $a_m + mb_m$ at step $m$ and you are bound to guess right eventually.