Một con ếch nhảy xung quanh trên dãy số và bạn cố gắng bắt nó. Nhảy và bắt luôn luân phiên nhau. Con ếch bắt đầu ở vị trí \(s \in \mathbb{Z}\) và với mỗi lần di chuyển nó sẽ nhảy một khoảng cách \(z \in \mathbb{Z}\) (nếu \(z>0\) , nó sẽ nhảy ở bên phải, ngược lại nếu ở bên trái). \(z\) giống nhau cho mọi bước nhảy. Chụp nhanh bao gồm chỉ định một vị trí số nguyên. Người ta không biết \(z\) hay \(s\) . Chúng tôi chỉ ra rằng có một cách luôn luôn bắt được con ếch.
Trước hết, \(a_1 = s\) và \(a_{n+1} = a_n + z = s + n \cdot z\) với \(s,z \in \mathbb{Z}\) .
Chúng tôi chọn bây giờ
$$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 ) $$
dưới dạng hàm gán (chính xác) một bộ số nguyên cho mọi số tự nhiên. Sự lựa chọn của hàm này là thông qua các hàm \(f(n) = (-1)^n \left \lfloor \frac{n}{2} \right \rfloor\) , \(\mathbb{N}\) trên \(\mathbb{Z}\) và \(g(2^kr) = (k+1, \frac{r+1}{2})\) , \(\mathbb{N}\) trên \(\mathbb{N}^2\) lập bản đồ một cách khách quan, có động cơ.
Bây giờ chúng tôi cho thấy tính khách quan của \(h\) ( \(h\) cũng không ảnh hưởng, nhưng chúng tôi không cần thuộc tính này).
Cho \((x,y) = (2^{k_1} r_1, 2^{k_2} r_2) \in\mathbb{Z}^2\) . Nhưng sau đó
$$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).$$
Do đó: \(\forall (s,z) \in \mathbb{Z}^2 \, \exists \, m \in \mathbb{N}\) với \(h(m) = (x_m,y_m) = (s, z)\) .
Ví dụ: nếu đến lượt chúng ta di chuyển tại \(n = 88\) , chúng ta tính \(h(88)=(2,3)\) và chọn \(2 + 88 \cdot 3 = 266\) làm vị trí.
Sau đó, sau khi di chuyển chính xác \(m\) với \(x_m + m \cdot y_m = s + m \cdot z = a_m\) , lựa chọn thuộc về con ếch.
Ngoài \(h\) , có thể có nhiều chức năng khác như chức năng ghép nối Cantor hoặc một đường xoắn ốc bijective .
Đây là một triển khai đơn giản trong JavaScript:
See the Pen catch the frog by David Vielhuber (@vielhuber) on CodePen.