Rano saltas sur nombrolinio, kaj la celo estas kapti ĝin. Saltado kaj kaptado alternas. La rano komencas ĉe pozicio \(s \in \mathbb{Z}\) kaj kun ĉiu movo, ĝi saltas distancon de \(z \in \mathbb{Z}\) (se \(z>0\) , ĝi saltas dekstren; alie, maldekstren). \(z\) estas la sama por ĉiu salto. Kapti la ranon implicas specifi entjeran pozicion. Nek \(z\) nek \(s\) estas konataj. Ni montros, ke ekzistas proceduro, kiu ĉiam permesas al ni kapti la ranon.
Unue, \(a_1 = s\) kaj \(a_{n+1} = a_n + z = s + n \cdot z\) kun \(s,z \in \mathbb{Z}\) .
Ni elektas nun
$$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 ) $$
kiel la funkcio, kiu atribuas (ekzakte) nombran opon de tutaj nombroj al ĉiu natura nombro. La elekto de ĉi tiu funkcio estas per la funkcioj \(f(n) = (-1)^n \left \lfloor \frac{n}{2} \right \rfloor\) , la \(\mathbb{N}\) sur \(\mathbb{Z}\) kaj \(g(2^kr) = (k+1, \frac{r+1}{2})\) , kiu \(\mathbb{N}\) sur \(\mathbb{N}^2\) mapo objektive, motivita.
Ni nun montras la surjektivecon de \(h\) ( \(h\) ankaŭ estas injektiva, sed ni ne bezonas ĉi tiun econ).
Lasu \((x,y) = (2^{k_1} r_1, 2^{k_2} r_2) \in\mathbb{Z}^2\) . Sed tiam
$$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).$$
Sekve: \(\forall (s,z) \in \mathbb{Z}^2 \, \exists \, m \in \mathbb{N}\) kun \(h(m) = (x_m,y_m) = (s, z)\) .
Ekzemple, se estas nia vico moviĝi ĉe \(n = 88\) , ni kalkulas \(h(88)=(2,3)\) kaj elektas \(2 + 88 \cdot 3 = 266\) kiel la pozicion.
Tiam post ekzakte \(m\) moviĝas per \(x_m + m \cdot y_m = s + m \cdot z = a_m\) la elekto falas sur la ranon.
Aldone al \(h\) , multaj aliaj funkcioj kiel ekzemple pariga funkcio de Cantor aŭ biokipa spiralo eblas.
Jen simpla efektivigo en Ĝavoskripto:
See the Pen catch the frog by David Vielhuber (@vielhuber) on CodePen.