Kaptu ranojn

Rano saltas ĉirkaŭ la numeran linion kaj vi provas kapti ĝin. Saltado kaj kaptado ĉiam alternas. La rano komencas ĉe pozicio \(s \in \mathbb{Z}\) kaj per ĉiu movo ĝi saltas distancon de \(z \in \mathbb{Z}\) (se \(z>0\) , ĝi saltas dekstre, alie se maldekstre). \(z\) estas la sama por ĉiu salto. Klako konsistas el specifado de entjera pozicio. Oni scias nek \(z\) nek \(s\) . Ni montras, ke ekzistas maniero ĉiam 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 Cantorbiokipa spiralo eblas.

Jen simpla efektivigo en Ĝavoskripto:

See the Pen catch the frog by David Vielhuber (@vielhuber) on CodePen.

Reen