Una rana salta su una retta numerica e l'obiettivo è catturarla. Saltare e catturare si alternano. La rana parte dalla posizione \(s \in \mathbb{Z}\) e ad ogni mossa salta di una distanza \(z \in \mathbb{Z}\) (se \(z>0\) , salta a destra; altrimenti, a sinistra). \(z\) è lo stesso per ogni salto. Catturare la rana implica specificare una posizione intera. Né \(z\) né \(s\) sono noti. Dimostreremo che esiste una procedura che ci permette sempre di catturare 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.