En groda hoppar runt på en tallinje, och målet är att fånga den. Att hoppa och fånga varvas. Grodan börjar vid position \(s \in \mathbb{Z}\) och med varje drag hoppar den en sträcka av \(z \in \mathbb{Z}\) (om \(z>0\) hoppar den åt höger; annars åt vänster). \(z\) är densamma för varje hopp. Att fånga grodan innebär att ange en heltalsposition. Varken \(z\) eller \(s\) är kända. Vi ska visa att det finns en procedur som alltid tillåter oss att fånga grodan.
Först och främst \(a_1 = s\) och \(a_{n+1} = a_n + z = s + n \cdot z\) med \(s,z \in \mathbb{Z}\) .
Vi väljer 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 som tilldelar (exakt) ett taltal av heltal till varje naturligt tal. Valet av denna funktion sker genom funktionerna \(f(n) = (-1)^n \left \lfloor \frac{n}{2} \right \rfloor\) , \(\mathbb{N}\) på \(\mathbb{Z}\) och \(g(2^kr) = (k+1, \frac{r+1}{2})\) , vilken \(\mathbb{N}\) på \(\mathbb{N}^2\) karta med motiv, motiverad.
Vi visar nu överföringsförmågan för \(h\) ( \(h\) är också injektiv, men vi behöver inte den här egenskapen).
Låt \((x,y) = (2^{k_1} r_1, 2^{k_2} r_2) \in\mathbb{Z}^2\) . Men då
$$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).$$
Därav: \(\forall (s,z) \in \mathbb{Z}^2 \, \exists \, m \in \mathbb{N}\) med \(h(m) = (x_m,y_m) = (s, z)\) .
Om det till exempel är vår tur att flytta vid \(n = 88\) , beräknar vi \(h(88)=(2,3)\) och väljer \(2 + 88 \cdot 3 = 266\) som position.
Efter exakt \(m\) rör sig med \(x_m + m \cdot y_m = s + m \cdot z = a_m\) faller valet på grodan.
Förutom \(h\) är många andra funktioner som Cantors parningsfunktion eller en bijektiv spiral möjliga.
Här är en enkel implementering i JavaScript:
See the Pen catch the frog by David Vielhuber (@vielhuber) on CodePen.