En groda hoppar runt på nummerlinjen och du försöker fånga den. Hoppning och fånga växlar alltid. Grodan börjar vid position \(s \in \mathbb{Z}\) och för varje drag hoppar den avståndet \(z \in \mathbb{Z}\) (om \(z>0\) hoppar den till höger, annars till vänster). \(z\) är densamma för varje hopp. Snapping består av att ange en heltalsposition. Man vet varken \(z\) eller \(s\) . Vi visar att det finns ett sätt att alltid 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.