Een kikker springt rond op een getallenlijn en het doel is om hem te vangen. Springen en vangen wisselen elkaar af. De kikker begint op positie \(s \in \mathbb{Z}\) en springt bij elke beweging een afstand van \(z \in \mathbb{Z}\) (als \(z>0\) , springt hij naar rechts; anders naar links). \(z\) is bij elke sprong hetzelfde. Om de kikker te vangen, moet een integerpositie worden opgegeven. Noch \(z\) noch \(s\) is bekend. We zullen aantonen dat er een procedure bestaat waarmee we de kikker altijd kunnen vangen.
Allereerst \(a_1 = s\) en \(a_{n+1} = a_n + z = s + n \cdot z\) met \(s,z \in \mathbb{Z}\) .
We kiezen 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 ) $$
als de functie die (exact) een tupel van hele getallen toekent aan elk natuurlijk getal. De keuze van deze functie is via de functies \(f(n) = (-1)^n \left \lfloor \frac{n}{2} \right \rfloor\) , de \(\mathbb{N}\) op \(\mathbb{Z}\) en \(g(2^kr) = (k+1, \frac{r+1}{2})\) , welke \(\mathbb{N}\) op \(\mathbb{N}^2\) kaart bijectief, gemotiveerd.
We laten nu zien dat de surjectiviteit van \(h\) ( \(h\) ook injectief is, maar we hebben deze eigenschap niet nodig).
Laat \((x,y) = (2^{k_1} r_1, 2^{k_2} r_2) \in\mathbb{Z}^2\) . Maar dan
$$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).$$
Vandaar: \(\forall (s,z) \in \mathbb{Z}^2 \, \exists \, m \in \mathbb{N}\) met \(h(m) = (x_m,y_m) = (s, z)\) .
Als het bijvoorbeeld onze beurt is om \(n = 88\) , berekenen we \(h(88)=(2,3)\) en kiezen \(2 + 88 \cdot 3 = 266\) als positie.
Na exact \(m\) met \(x_m + m \cdot y_m = s + m \cdot z = a_m\) valt de keuze op de kikker.
Naast \(h\) zijn vele andere functies mogelijk, zoals de paringsfunctie van Cantor of een bijectieve spiraal .
Hier is een eenvoudige implementatie in JavaScript:
See the Pen catch the frog by David Vielhuber (@vielhuber) on CodePen.