Seekor katak melompat-lompat di garis bilangan, dan tujuannya adalah untuk menangkapnya. Melompat dan menangkap bergantian. Katak memulai pada posisi \(s \in \mathbb{Z}\) dan dengan setiap gerakan, ia melompat sejauh \(z \in \mathbb{Z}\) (jika \(z>0\) , ia melompat ke kanan; jika tidak, ke kiri). \(z\) sama untuk setiap lompatan. Menangkap katak melibatkan penentuan posisi bilangan bulat. Baik \(z\) maupun \(s\) tidak diketahui. Kita akan menunjukkan bahwa ada prosedur yang selalu memungkinkan kita untuk menangkap katak.
Pertama-tama, \(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 menetapkan (persis) sejumlah tupel bilangan bulat ke setiap bilangan asli. 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}\) pada \(\mathbb{N}^2\) memetakan secara subjektif, termotivasi.
Kami sekarang menunjukkan dugaan \(h\) ( \(h\) juga injeksi, tapi kami tidak membutuhkan properti ini).
Misalkan \((x,y) = (2^{k_1} r_1, 2^{k_2} r_2) \in\mathbb{Z}^2\) . Tapi 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).$$
Karenanya: \(\forall (s,z) \in \mathbb{Z}^2 \, \exists \, m \in \mathbb{N}\) dengan \(h(m) = (x_m,y_m) = (s, z)\) .
Misalnya, jika giliran kita untuk bergerak di \(n = 88\) , kita menghitung \(h(88)=(2,3)\) dan memilih \(2 + 88 \cdot 3 = 266\) sebagai posisinya.
Kemudian setelah tepat \(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 bijektiva yang dimungkinkan.
Berikut ini implementasi sederhana dalam JavaScript:
See the Pen catch the frog by David Vielhuber (@vielhuber) on CodePen.