Una rana salta en una recta numérica y el objetivo es atraparla. Saltar y atrapar 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 a la derecha; de lo contrario, a la izquierda). \(z\) es la misma para cada salto. Atrapar a la rana implica especificar una posición entera. Ni \(z\) ni \(s\) se conocen. Demostraremos que existe un procedimiento que siempre nos permite atrapar a 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.