Kurbağaları yakala

Sayı doğrusunda bir kurbağa atlar ve onu yakalamaya çalışırsınız. Zıplama ve yakalama her zaman değişmeli. Kurbağa \(s \in \mathbb{Z}\) ve her hareketinde \(z \in \mathbb{Z}\) mesafesine atlar (eğer \(z>0\) , atlar sağa, aksi takdirde sola). \(z\) her atlamada aynıdır. Yapışma, bir tamsayı konumu belirtmekten oluşur. Kişi ne \(z\) ne de \(s\) bilir. Kurbağayı her zaman yakalamanın bir yolu olduğunu gösteriyoruz.


Her şeyden önce, \(a_1 = s\) ve \(a_{n+1} = a_n + z = s + n \cdot z\) ile \(s,z \in \mathbb{Z}\) .

Şimdi seçiyoruz 

$$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 ) $$

her doğal sayıya (tam olarak) bir tam sayı demeti atayan işlev olarak. Bu işlevin seçimi \(f(n) = (-1)^n \left \lfloor \frac{n}{2} \right \rfloor\) , \(\mathbb{N}\) \(\mathbb{Z}\) ve \(g(2^kr) = (k+1, \frac{r+1}{2})\) üzerinde \(\mathbb{N}\) \(\mathbb{N}^2\) motive edilmiş, iki taraflı eşleyin.

Şimdi \(h\) ( \(h\) nin yüzeyselliğinin de enjekte edici olduğunu gösteriyoruz, ancak bu özelliğe ihtiyacımız yok).

\((x,y) = (2^{k_1} r_1, 2^{k_2} r_2) \in\mathbb{Z}^2\) . Ama sonra

$$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).$$

Dolayısıyla: \(\forall (s,z) \in \mathbb{Z}^2 \, \exists \, m \in \mathbb{N}\) \(h(m) = (x_m,y_m) = (s, z)\) .

Örneğin, \(n = 88\) hareket etme sırası bizdeyse, \(n = 88\) \(h(88)=(2,3)\) hesaplayıp konum olarak \(2 + 88 \cdot 3 = 266\) seçiyoruz.

Daha sonra \(m\) , \(x_m + m \cdot y_m = s + m \cdot z = a_m\) ile tam olarak hareket \(x_m + m \cdot y_m = s + m \cdot z = a_m\) sonra seçim kurbağaya düşer.

\(h\) ye ek olarak, Cantor'un eşleştirme işlevi veya önyargılı bir spiral gibi birçok başka işlev de mümkündür.

İşte JavaScript'te basit bir uygulama:

See the Pen catch the frog by David Vielhuber (@vielhuber) on CodePen.

Geri