Një bretkocë kërcen përreth në vijën e numrave dhe ju përpiqeni ta kapni atë. Kërcimi dhe kapja gjithmonë janë alternative. Bretkosa fillon në pozicionin \(s \in \mathbb{Z}\) dhe me çdo lëvizje ajo kërcen një distancë prej \(z \in \mathbb{Z}\) (nëse \(z>0\) , ajo kërcen në të djathtë, përndryshe nëse në të majtë). \(z\) është e njëjtë për çdo kërcim. Kërcimi konsiston në specifikimin e një pozicioni të plotë. Dikush nuk njeh as \(z\) dhe as \(s\) . Ne tregojmë se ekziston një mënyrë për të kapur gjithmonë bretkosën.
Para së gjithash, \(a_1 = s\) dhe \(a_{n+1} = a_n + z = s + n \cdot z\) me \(s,z \in \mathbb{Z}\) .
Ne zgjedhim tani
$$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 ) $$
si funksion që cakton (saktësisht) një numër numrash të plotë të çdo numri natyror. Zgjedhja e këtij funksioni bëhet përmes funksioneve \(f(n) = (-1)^n \left \lfloor \frac{n}{2} \right \rfloor\) , \(\mathbb{N}\) në \(\mathbb{Z}\) dhe \(g(2^kr) = (k+1, \frac{r+1}{2})\) , i cili \(\mathbb{N}\) në \(\mathbb{N}^2\) hartë biektivisht, e motivuar.
Tani tregojmë se sygjerueshmëria e \(h\) ( \(h\) është gjithashtu e dëmshme, por nuk na duhet kjo pronë).
Le të \((x,y) = (2^{k_1} r_1, 2^{k_2} r_2) \in\mathbb{Z}^2\) . Por pastaj
$$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).$$
Prandaj: \(\forall (s,z) \in \mathbb{Z}^2 \, \exists \, m \in \mathbb{N}\) me \(h(m) = (x_m,y_m) = (s, z)\) .
Për shembull, nëse është rradha jonë tek \(n = 88\) , ne llogarisim \(h(88)=(2,3)\) dhe zgjedhim \(2 + 88 \cdot 3 = 266\) si pozicion.
Pastaj pasi të lëvizë saktësisht \(m\) me \(x_m + m \cdot y_m = s + m \cdot z = a_m\) zgjedhja bie në bretkocë.
Përveç \(h\) , shumë funksione të tjera të tilla si funksioni i çiftimit të Cantor ose një spirale biektive janë të mundshme.
Këtu është një implementim i thjeshtë në JavaScript:
See the Pen catch the frog by David Vielhuber (@vielhuber) on CodePen.