Une grenouille se déplace sur une droite numérique, et le but est de l'attraper. Les sauts et les attraper alternent. La grenouille part de la position \(s \in \mathbb{Z}\) et, à chaque déplacement, elle saute d'une distance \(z \in \mathbb{Z}\) (si \(z>0\) , elle saute vers la droite ; sinon, vers la gauche). \(z\) est la même pour chaque saut. Attraper la grenouille implique de spécifier une position entière. Ni \(z\) ni \(s\) ne sont connus. Nous allons montrer qu'il existe une procédure qui permet toujours d'attraper 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.