Tangkap katak

Seekor katak melompat di garis nombor dan anda cuba menangkapnya. Melompat dan menangkap selalu bergantian. Katak bermula di kedudukan \(s \in \mathbb{Z}\) dan dengan setiap pergerakannya melompat jarak \(z \in \mathbb{Z}\) (jika \(z>0\) , ia melompat ke kanan, jika tidak ke kiri). \(z\) adalah sama untuk setiap lompatan. Snapping terdiri daripada menentukan kedudukan integer. Seseorang tidak tahu \(z\) atau \(s\) . Kami menunjukkan bahawa ada cara untuk selalu 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.

Belakang