Ένας βάτραχος πηδάει πάνω σε μια αριθμογραμμή και ο στόχος είναι να τον πιάσει. Το άλμα και το πιάσιμο εναλλάσσονται. Ο βάτραχος ξεκινά από τη θέση \(s \in \mathbb{Z}\) και με κάθε κίνηση, πηδάει μια απόσταση \(z \in \mathbb{Z}\) (αν \(z>0\) , πηδάει προς τα δεξιά· διαφορετικά, προς τα αριστερά). Το \(z\) είναι το ίδιο για κάθε άλμα. Το πιάσιμο του βατράχου περιλαμβάνει τον καθορισμό μιας ακέραιης θέσης. Ούτε \(z\) ούτε \(s\) είναι γνωστά. Θα δείξουμε ότι υπάρχει μια διαδικασία που μας επιτρέπει πάντα να πιάνουμε τον βάτραχο.
Πρώτα απ 'όλα, \(a_1 = s\) και \(a_{n+1} = a_n + z = s + n \cdot z\) με \(s,z \in \mathbb{Z}\) .
Επιλέγουμε τώρα
$$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 ) $$
ως συνάρτηση που εκχωρεί (ακριβώς) μια πλειάδα αριθμών ολόκληρων αριθμών σε κάθε φυσικό αριθμό. Η επιλογή αυτής της συνάρτησης είναι μέσω των συναρτήσεων \(f(n) = (-1)^n \left \lfloor \frac{n}{2} \right \rfloor\) , το \(\mathbb{N}\) on \(\mathbb{Z}\) και \(g(2^kr) = (k+1, \frac{r+1}{2})\) , το οποίο \(\mathbb{N}\) \(\mathbb{N}^2\) χάρτης bijectively, κίνητρο.
Δείχνουμε τώρα ότι η εκθετικότητα του \(h\) ( \(h\) είναι επίσης ενέσιμη, αλλά δεν χρειαζόμαστε αυτήν την ιδιότητα).
Let \((x,y) = (2^{k_1} r_1, 2^{k_2} r_2) \in\mathbb{Z}^2\) . Αλλά στη συνέχεια
$$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).$$
Ως εκ τούτου: \(\forall (s,z) \in \mathbb{Z}^2 \, \exists \, m \in \mathbb{N}\) με \(h(m) = (x_m,y_m) = (s, z)\) .
Για παράδειγμα, αν είναι η σειρά μας να κινηθούμε στο \(n = 88\) , υπολογίζουμε \(h(88)=(2,3)\) και επιλέγουμε \(2 + 88 \cdot 3 = 266\) ως τη θέση.
Στη συνέχεια, μετά ακριβώς \(m\) κινείται με \(x_m + m \cdot y_m = s + m \cdot z = a_m\) η επιλογή πέφτει στον βάτραχο.
Εκτός από το \(h\) , είναι δυνατές πολλές άλλες λειτουργίες, όπως η λειτουργία ζευγαρώματος του Cantor ή μια bijective spiral .
Εδώ είναι μια απλή εφαρμογή σε JavaScript:
See the Pen catch the frog by David Vielhuber (@vielhuber) on CodePen.