Seekor katak melompat-lompat pada garis nombor, dan matlamatnya adalah untuk menangkapnya. Melompat dan menangkap secara berselang-seli. Katak bermula pada kedudukan \(s \in \mathbb{Z}\) dan dengan setiap pergerakan, ia melompat sejauh \(z \in \mathbb{Z}\) (jika \(z>0\) , ia melompat ke kanan; jika tidak, ke kiri). \(z\) adalah sama untuk setiap lompatan. Menangkap katak melibatkan penentuan kedudukan integer. Baik \(z\) mahupun \(s\) tidak diketahui. Kami akan menunjukkan bahawa terdapat prosedur yang sentiasa membolehkan kita menangkap katak.
Pertama sekali, \(a_1 = s\) dan \(a_{n+1} = a_n + z = s + n \cdot z\) dengan \(s,z \in \mathbb{Z}\) .
Kami memilih sekarang
$$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 ) $$
sebagai fungsi yang memberikan (tepat) bilangan tupel nombor bulat kepada setiap nombor semula jadi. Pilihan fungsi ini adalah melalui fungsi \(f(n) = (-1)^n \left \lfloor \frac{n}{2} \right \rfloor\) , \(\mathbb{N}\) pada \(\mathbb{Z}\) dan \(g(2^kr) = (k+1, \frac{r+1}{2})\) , yang \(\mathbb{N}\) \(\mathbb{N}^2\) peta secara objektif, bermotivasi.
Kami sekarang menunjukkan kejelasan \(h\) ( \(h\) juga bersifat suntikan, tetapi kita tidak memerlukan sifat ini).
Biarkan \((x,y) = (2^{k_1} r_1, 2^{k_2} r_2) \in\mathbb{Z}^2\) . Tetapi kemudian
$$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).$$
Oleh itu: \(\forall (s,z) \in \mathbb{Z}^2 \, \exists \, m \in \mathbb{N}\) dengan \(h(m) = (x_m,y_m) = (s, z)\) .
Sebagai contoh, jika giliran kita di \(n = 88\) , kita mengira \(h(88)=(2,3)\) dan memilih \(2 + 88 \cdot 3 = 266\) sebagai kedudukan.
Kemudian setelah betul-betul \(m\) bergerak dengan \(x_m + m \cdot y_m = s + m \cdot z = a_m\) pilihan jatuh pada katak.
Selain \(h\) , banyak fungsi lain seperti fungsi pasangan Cantor atau spiral bijektif juga mungkin dilakukan.
Berikut adalah pelaksanaan sederhana dalam JavaScript:
See the Pen catch the frog by David Vielhuber (@vielhuber) on CodePen.