Una rana salta sulla linea dei numeri e tu cerchi di prenderla. Saltare e riprendere si alternano sempre. La rana parte dalla posizione \(s \in \mathbb{Z}\) e ad ogni movimento salta per una distanza di \(z \in \mathbb{Z}\) (se \(z>0\) , salta a destra, altrimenti se a sinistra). \(z\) è lo stesso per ogni salto. Lo snap consiste nello specificare una posizione intera. Non si conosce né \(z\) né \(s\) . Dimostriamo che c'è un modo per catturare sempre la rana.
Prima di tutto, \(a_1 = s\) e \(a_{n+1} = a_n + z = s + n \cdot z\) con \(s,z \in \mathbb{Z}\) .
Scegliamo adesso
$$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 ) $$
come la funzione che assegna (esattamente) una tupla di numeri interi a ogni numero naturale. La scelta di questa funzione avviene tramite le funzioni \(f(n) = (-1)^n \left \lfloor \frac{n}{2} \right \rfloor\) , il \(\mathbb{N}\) su \(\mathbb{Z}\) e \(g(2^kr) = (k+1, \frac{r+1}{2})\) , che \(\mathbb{N}\) su \(\mathbb{N}^2\) mappare biologicamente, motivato.
Ora mostriamo la suriettività di \(h\) (anche \(h\) è iniettiva, ma non abbiamo bisogno di questa proprietà).
Sia \((x,y) = (2^{k_1} r_1, 2^{k_2} r_2) \in\mathbb{Z}^2\) . Ma allora
$$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).$$
Quindi: \(\forall (s,z) \in \mathbb{Z}^2 \, \exists \, m \in \mathbb{N}\) con \(h(m) = (x_m,y_m) = (s, z)\) .
Ad esempio, se è il nostro turno di muoverci a \(n = 88\) , calcoliamo \(h(88)=(2,3)\) e selezioniamo \(2 + 88 \cdot 3 = 266\) come posizione.
Quindi dopo che esattamente \(m\) muove con \(x_m + m \cdot y_m = s + m \cdot z = a_m\) la scelta ricade sulla rana.
Oltre a \(h\) , sono possibili molte altre funzioni come la funzione di accoppiamento di Cantor o una spirale biiettiva .
Ecco una semplice implementazione in JavaScript:
See the Pen catch the frog by David Vielhuber (@vielhuber) on CodePen.