Een kikker springt rond op de getallenlijn en jij probeert hem te vangen. Springen en vangen wisselen elkaar altijd 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 hetzelfde voor elke sprong. Snappen bestaat uit het specificeren van een gehele positie. Men kent noch \(z\) noch \(s\) . We laten zien dat er altijd een manier is om de kikker te 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.