Ένας βάτραχος πηδάει στη γραμμή αριθμών και προσπαθείτε να τον πιάσετε. Το άλμα και η σύλληψη είναι πάντα εναλλακτικά. Ο βάτραχος ξεκινά στη θέση \(s \in \mathbb{Z}\) και με κάθε κίνηση πηδά μια απόσταση \(z \in \mathbb{Z}\) (εάν \(z>0\) , πηδά προς τα δεξιά, αλλιώς εάν προς τα αριστερά). \(z\) είναι το ίδιο για κάθε άλμα. Το Snapping συνίσταται στον καθορισμό ακέραιας θέσης. Δεν ξέρει ούτε \(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.