En frø hopper rundt på en tallinje, og målet er at fange den. Hopping og gribning skiftes til. Frøen starter ved position \(s \in \mathbb{Z}\) , og med hvert træk hopper den en afstand på \(z \in \mathbb{Z}\) (hvis \(z>0\) , hopper den til højre; ellers til venstre). \(z\) er den samme for hvert hop. At fange frøen indebærer at angive en heltalsposition. Hverken \(z\) eller \(s\) er kendt. Vi vil vise, at der er en procedure, der altid tillader os at fange frøen.
Først og fremmest \(a_1 = s\) og \(a_{n+1} = a_n + z = s + n \cdot z\) med \(s,z \in \mathbb{Z}\) .
Vi vælger nu
$$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 ) $$
som den funktion, der tildeler (nøjagtigt) et taltal af hele tal til hvert naturligt tal. Valget af denne funktion sker gennem funktionerne \(f(n) = (-1)^n \left \lfloor \frac{n}{2} \right \rfloor\) , \(\mathbb{N}\) på \(\mathbb{Z}\) og \(g(2^kr) = (k+1, \frac{r+1}{2})\) , hvilken \(\mathbb{N}\) på \(\mathbb{N}^2\) kort vedhængende, motiveret.
Vi viser nu, at \(h\) ( \(h\) også er injektionsdygtig, men vi har ikke brug for denne egenskab).
Lad \((x,y) = (2^{k_1} r_1, 2^{k_2} r_2) \in\mathbb{Z}^2\) . Men derefter
$$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).$$
Derfor: \(\forall (s,z) \in \mathbb{Z}^2 \, \exists \, m \in \mathbb{N}\) med \(h(m) = (x_m,y_m) = (s, z)\) .
For eksempel, hvis det er vores tur at bevæge sig ved \(n = 88\) , beregner vi \(h(88)=(2,3)\) og vælger \(2 + 88 \cdot 3 = 266\) som position.
Derefter falder valget på frøen efter nøjagtigt \(m\) bevæger sig med \(x_m + m \cdot y_m = s + m \cdot z = a_m\) .
Ud over \(h\) er mange andre funktioner såsom Cantors parringsfunktion eller en bijektiv spiral mulig.
Her er en simpel implementering i JavaScript:
See the Pen catch the frog by David Vielhuber (@vielhuber) on CodePen.