Frösche fangen

Ein Frosch springt auf dem Zahlenstrahl umher und man versucht ihn zu fangen. Dabei wechseln sich Springen und Fangen stets ab. Der Frosch startet an Position \(s \in \mathbb{Z}\) und bei jedem Zug springt er eine Distanz von \(z \in \mathbb{Z}\) (falls \(z>0\), springt er nach rechts, anderen falls nach links). \(z\) ist bei jedem Sprung gleich. Das Fangen besteht aus der Angabe einer ganzzahligen Position. Man kennt weder \(z\) noch \(s\). Wir zeigen, dass es eine Vorgehensweise gibt, mit der man stets den Frosch fängt.


Zunächst ist \(a_1 = s\) und \(a_{n+1} = a_n + z = s + n \cdot z\) mit \(s,z \in \mathbb{Z}\).

Wir wählen 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 ) $$

als diejenige Funktion, die jeder natürlichen Zahl (genau) ein Zahlentupel ganzer Zahlen zuordnet. Die Wahl dieser Funktion ist durch die Funktionen \(f(n) = (-1)^n \left \lfloor \frac{n}{2} \right \rfloor\), die \(\mathbb{N}\) auf \(\mathbb{Z}\) sowie \(g(2^k r) = (k+1, \frac{r+1}{2})\), die \(\mathbb{N}\) auf \(\mathbb{N}^2\) bijektiv abbilden, motiviert.

Wir zeigen nun die Surjektivität von \(h\) (\(h\) ist auch injektiv, diese Eigenschaft benötigen wir jedoch nicht).

Sei \((x,y) = (2^{k_1} r_1, 2^{k_2} r_2) \in\mathbb{Z}^2\). Dann ist aber

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

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

Sind wir beispielsweise am Zug bei \(n = 88\), berechnen wir \(h(88)=(2,3)\) und wählen als Position \(2 + 88 \cdot 3 = 266\).

Dann fällt aber nach genau \(m\) Zügen mit \(x_m + m \cdot y_m = s + m \cdot z = a_m\) die Wahl auf den Frosch.

Neben \(h\) sind noch viele andere Funktionen wie die Cantorsche Paarungsfunktion oder eine bijektive Spirale möglich.

Es folgt eine einfache Implementierung in JavaScript:

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

Zurück