Fang frøer

En frø hopper rundt på nummerlinjen, og du prøver at fange den. Spring og fangst skifter altid. Frøen starter ved position \(s \in \mathbb{Z}\) og med hvert træk springer den en afstand på \(z \in \mathbb{Z}\) (hvis \(z>0\) , hopper den til højre, ellers hvis til venstre). \(z\) er den samme for hvert spring. Snapping består i at angive en heltalsposition. Man kender hverken \(z\) eller \(s\) . Vi viser, at der altid er en måde at fange frøen på.


Først og fremmest \(a_1 = s\) og \(a_{n+1} = a_n + z = s + n \cdot z\) med \(s,z \in \mathbb{Z}\) .

Vi vælger nu 

$$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 ) $$

som den funktion, der tildeler (nøjagtigt) et taltal af hele tal til hvert naturligt tal. Valget af denne funktion sker gennem funktionerne \(f(n) = (-1)^n \left \lfloor \frac{n}{2} \right \rfloor\) , \(\mathbb{N}\)\(\mathbb{Z}\) og \(g(2^kr) = (k+1, \frac{r+1}{2})\) , hvilken \(\mathbb{N}\)\(\mathbb{N}^2\) kort vedhængende, motiveret.

Vi viser nu, at \(h\) ( \(h\) også er injektionsdygtig, men vi har ikke brug for denne egenskab).

Lad \((x,y) = (2^{k_1} r_1, 2^{k_2} r_2) \in\mathbb{Z}^2\) . Men derefter

$$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).$$

Derfor: \(\forall (s,z) \in \mathbb{Z}^2 \, \exists \, m \in \mathbb{N}\) med \(h(m) = (x_m,y_m) = (s, z)\) .

For eksempel, hvis det er vores tur at bevæge sig ved \(n = 88\) , beregner vi \(h(88)=(2,3)\) og vælger \(2 + 88 \cdot 3 = 266\) som position.

Derefter falder valget på frøen efter nøjagtigt \(m\) bevæger sig med \(x_m + m \cdot y_m = s + m \cdot z = a_m\) .

Ud over \(h\) er mange andre funktioner såsom Cantors parringsfunktion eller en bijektiv spiral mulig.

Her er en simpel implementering i JavaScript:

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

Tilbage