Une grenouille saute sur la droite numérique et vous essayez de l'attraper. Sauter et attraper alternent toujours. La grenouille commence à la position \(s \in \mathbb{Z}\) et à chaque mouvement, elle saute d'une distance de \(z \in \mathbb{Z}\) (si \(z>0\) , elle saute à droite, sinon à gauche). \(z\) est le même pour chaque saut. L'accrochage consiste à spécifier une position entière. On ne connaît ni \(z\) ni \(s\) . Nous montrons qu'il existe un moyen d'attraper toujours la grenouille.
Tout d'abord, \(a_1 = s\) et \(a_{n+1} = a_n + z = s + n \cdot z\) avec \(s,z \in \mathbb{Z}\) .
Nous choisissons maintenant
$$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 ) $$
comme fonction qui assigne (exactement) un nombre tuple de nombres entiers à chaque nombre naturel. Le choix de cette fonction se fait à travers les fonctions \(f(n) = (-1)^n \left \lfloor \frac{n}{2} \right \rfloor\) , le \(\mathbb{N}\) sur \(\mathbb{Z}\) et \(g(2^kr) = (k+1, \frac{r+1}{2})\) , qui \(\mathbb{N}\) sur \(\mathbb{N}^2\) map bijectivement, motivé.
Nous montrons maintenant la surjectivité de \(h\) ( \(h\) est également injective, mais nous n'avons pas besoin de cette propriété).
Soit \((x,y) = (2^{k_1} r_1, 2^{k_2} r_2) \in\mathbb{Z}^2\) . Mais alors
$$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).$$
Par conséquent: \(\forall (s,z) \in \mathbb{Z}^2 \, \exists \, m \in \mathbb{N}\) avec \(h(m) = (x_m,y_m) = (s, z)\) .
Par exemple, si c'est à notre tour de se déplacer à \(n = 88\) , nous calculons \(h(88)=(2,3)\) et sélectionnons \(2 + 88 \cdot 3 = 266\) comme position.
Puis après exactement \(m\) se déplace avec \(x_m + m \cdot y_m = s + m \cdot z = a_m\) le choix tombe sur la grenouille.
En plus de \(h\) , de nombreuses autres fonctions telles que la fonction d'appariement de Cantor ou une spirale bijective sont possibles.
Voici une implémentation simple en JavaScript:
See the Pen catch the frog by David Vielhuber (@vielhuber) on CodePen.