12
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ This sounds like a (Martin Gardner?) problem I have heard before, only that one involved bombing a submarine instead of findind a frog. $\endgroup$ – Mike Pierce Dec 30 '14 at 20:04
  • $\begingroup$ I'm an eternal pacifist... $\endgroup$ – Oria Gruber Dec 30 '14 at 20:05
  • $\begingroup$ Leave the frogs alone. Experiment on yourselves. $\endgroup$ – Doug Spoonwood Dec 30 '14 at 20:07
  • $\begingroup$ 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). $\endgroup$ – Volodymyr Fomenko Dec 30 '14 at 20:07
  • $\begingroup$ 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. $\endgroup$ – Oria Gruber Dec 30 '14 at 20:08
24
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You got there before I did. $\endgroup$ – Mark Bennet Dec 30 '14 at 20:44
  • $\begingroup$ @Mark Bennet: better luck next time! $\endgroup$ – Rob Arthan Dec 30 '14 at 21:11
  • $\begingroup$ This even works if the frog's next position were determined by a Turing machine rather than a linear progression. (Even if the frog is privy to the positions you've guessed) $\endgroup$ – Milo Brandt Dec 31 '14 at 4:22
  • $\begingroup$ @Meelo: I don't see how you would deal with non-termination (unless you imposed a time bound on the frog's computation). $\endgroup$ – Rob Arthan Dec 31 '14 at 12:18
  • $\begingroup$ How does this work if you don't know what a and b are? $\endgroup$ – Some Guy Mar 15 '17 at 5:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.