Una rana salta sobre la recta numérica y tú intentas atraparla. Saltar y atrapar siempre se alternan. La rana comienza en la posición \(s \in \mathbb{Z}\) y con cada movimiento salta una distancia de \(z \in \mathbb{Z}\) (si \(z>0\) , salta hacia la derecha, de lo contrario si hacia la izquierda). \(z\) es el mismo para cada salto. El ajuste consiste en especificar una posición entera. Uno no conoce ni \(z\) ni \(s\) . Demostramos que hay una forma de atrapar siempre la rana.
En primer lugar, \(a_1 = s\) y \(a_{n+1} = a_n + z = s + n \cdot z\) con \(s,z \in \mathbb{Z}\) .
Elegimos ahora
$$h:\mathbb{N} \to \mathbb{Z}^2: h(2^k r) = \left ( (-1)^{k+1} \left \lfloor \frac{k+1}{2} \right \rfloor, (-1)^{\frac{r+1}{2}} \left \lfloor \frac{r+1}{4} \right \rfloor \right ) $$
como la función que asigna (exactamente) una tupla numérica de números enteros a cada número natural. La elección de esta función es a través de las funciones \(f(n) = (-1)^n \left \lfloor \frac{n}{2} \right \rfloor\) , el \(\mathbb{N}\) en \(\mathbb{Z}\) y \(g(2^kr) = (k+1, \frac{r+1}{2})\) , que \(\mathbb{N}\) en \(\mathbb{N}^2\) mapear bijetivamente, motivado.
Ahora mostramos la sobrejetividad de \(h\) ( \(h\) también es inyectiva, pero no necesitamos esta propiedad).
Sea \((x,y) = (2^{k_1} r_1, 2^{k_2} r_2) \in\mathbb{Z}^2\) . Pero entonces
$$h \left ( 2^{2 \cdot 2^{k_1} r_1 - 1} \cdot (4 \cdot 2^{k_2} r_2 - 1) \right ) = (2^{k_1} r_1, 2^{k_2} r_2) = (x,y).$$
Por tanto: \(\forall (s,z) \in \mathbb{Z}^2 \, \exists \, m \in \mathbb{N}\) con \(h(m) = (x_m,y_m) = (s, z)\) .
Por ejemplo, si es nuestro turno de movernos en \(n = 88\) , calculamos \(h(88)=(2,3)\) y seleccionamos \(2 + 88 \cdot 3 = 266\) como posición.
Luego, después de exactamente \(m\) mueve con \(x_m + m \cdot y_m = s + m \cdot z = a_m\) la elección recae en la rana.
Además de \(h\) , son posibles muchas otras funciones como la función de emparejamiento de Cantor o una espiral biyectiva .
Aquí hay una implementación simple en JavaScript:
See the Pen catch the frog by David Vielhuber (@vielhuber) on CodePen.