O broască sare pe linia numerică și încerci să o prinzi. Saltul și prinderea alternează întotdeauna. Broasca începe în poziția \(s \in \mathbb{Z}\) și la fiecare mișcare sare la o distanță de \(z \in \mathbb{Z}\) (dacă \(z>0\) , sare la dreapta, altfel dacă la stânga). \(z\) este același pentru fiecare salt. Snapping constă în specificarea unei poziții întregi. Nu se știe nici \(z\) nici \(s\) . Arătăm că există o modalitate de a prinde mereu broasca.
În primul rând, \(a_1 = s\) și \(a_{n+1} = a_n + z = s + n \cdot z\) cu \(s,z \in \mathbb{Z}\) .
Alegem acum
$$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 ) $$
ca funcție care atribuie (exact) un tuplu numeric de numere întregi la fiecare număr natural. Alegerea acestei funcții se face prin funcțiile \(f(n) = (-1)^n \left \lfloor \frac{n}{2} \right \rfloor\) , \(\mathbb{N}\) pe \(\mathbb{Z}\) și \(g(2^kr) = (k+1, \frac{r+1}{2})\) , care \(\mathbb{N}\) pe \(\mathbb{N}^2\) hartă bijectiv, motivată.
Acum arătăm că surjectivitatea lui \(h\) ( \(h\) este, de asemenea, injectivă, dar nu avem nevoie de această proprietate).
Fie \((x,y) = (2^{k_1} r_1, 2^{k_2} r_2) \in\mathbb{Z}^2\) . Dar apoi
$$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).$$
Prin urmare: \(\forall (s,z) \in \mathbb{Z}^2 \, \exists \, m \in \mathbb{N}\) cu \(h(m) = (x_m,y_m) = (s, z)\) .
De exemplu, dacă ne vine rândul să ne deplasăm la \(n = 88\) , calculăm \(h(88)=(2,3)\) și alegem poziția \(2 + 88 \cdot 3 = 266\) .
Apoi, după ce exact \(m\) se mută cu \(x_m + m \cdot y_m = s + m \cdot z = a_m\) alegerea cade pe broască.
În plus față de \(h\) , sunt posibile multe alte funcții, cum ar fi funcția de împerechere a lui Cantor sau o spirală bijectivă .
Iată o implementare simplă în JavaScript:
See the Pen catch the frog by David Vielhuber (@vielhuber) on CodePen.