Béka ugrál körbe a számegyenesen, és megpróbálja elkapni. Az ugrás és a fogás mindig váltakozik. A béka a \(s \in \mathbb{Z}\) pozícióból indul, és minden mozdulatával \(z \in \mathbb{Z}\) távolságot ugrik (ha \(z>0\) , akkor ugrik jobbra, különben ha balra). \(z\) minden ugrásnál megegyezik. A bepattintás egész szám megadásából áll. Az ember nem ismer sem \(z\) sem \(s\) . Megmutatjuk, hogy van mód arra, hogy mindig elkapjuk a békát.
Mindenekelőtt \(a_1 = s\) és \(a_{n+1} = a_n + z = s + n \cdot z\) a \(s,z \in \mathbb{Z}\) \(a_{n+1} = a_n + z = s + n \cdot z\) \(s,z \in \mathbb{Z}\) .
Most választunk
$$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 ) $$
mint függvény, amely minden természetes számhoz egész számokat ad (pontosan). Ezt a függvényt a \(f(n) = (-1)^n \left \lfloor \frac{n}{2} \right \rfloor\) , a \(\mathbb{N}\) on \(\mathbb{Z}\) és \(g(2^kr) = (k+1, \frac{r+1}{2})\) , amely \(\mathbb{N}\) \(\mathbb{N}^2\) térképet tisztességesen, motiválva.
Most megmutatjuk a \(h\) szurzivitását (a \(h\) is injektív, de nincs szükségünk erre a tulajdonságra).
Legyen \((x,y) = (2^{k_1} r_1, 2^{k_2} r_2) \in\mathbb{Z}^2\) . De aztán
$$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).$$
Ezért: \(\forall (s,z) \in \mathbb{Z}^2 \, \exists \, m \in \mathbb{N}\) a \(h(m) = (x_m,y_m) = (s, z)\) .
Például, ha rajtunk a sor, hogy a \(n = 88\) ponton mozogjunk, kiszámoljuk a \(h(88)=(2,3)\) \(2 + 88 \cdot 3 = 266\) és a \(2 + 88 \cdot 3 = 266\) pontot választjuk.
Aztán miután pontosan \(m\) mozog a \(x_m + m \cdot y_m = s + m \cdot z = a_m\) a választás a békára esik.
A \(h\) mellett számos más funkció is lehetséges, például Cantor párosítási funkciója vagy egy bijektív spirál .
Itt van egy egyszerű megvalósítás a JavaScript-ben:
See the Pen catch the frog by David Vielhuber (@vielhuber) on CodePen.