Puzzle: Dar un algoritmo para encontrar una rana que salta a lo largo de la recta numérica

Question

Estás jugando a un juego, tu objetivo en este juego es atrapar una rana que está saltando entre números naturales.

Al principio, la rana se encuentra en el número $a \in \mathbb N$ que no conoce. En cada turno, adivinas dónde se encuentra la rana.

Si aciertas, ganas.

Si te equivocas - la rana salta $b \in \mathbb N$ números a la derecha. Es decir, si te equivocaste en la primera adivinanza, la rana está ahora en $a+b$ . Si te vuelves a equivocar, ahora está en $a+2b$ .

Ni $a$ ou $b$ son conocidos por ti. Todo lo que sabes es que son números naturales.

Proponer un algoritmo que encuentre la rana en un número finito de pasos, independientemente de lo que $a$ y $b$ son.

Reto adicional: La misma pregunta, pero ahora $a,b \in \mathbb Z$ .

Answer 1

Para fijos $a$ y $b$ después de $m$ pasos, la rana estará en $a + mb$ si aún no has acertado. El conjunto de pares $(a, b) \in \mathbb{N}\times \mathbb{N}$ es contable, por lo que se puede enumerar, digamos como $(a_0, b_0), (a_1, b_1), \ldots$ . Ahora adivina $a_m + mb_m$ al paso $m$ y al final acertarás.