Một con ếch nhảy trên trục số, và mục tiêu là bắt nó. Việc nhảy và bắt diễn ra luân phiên. Con ếch bắt đầu ở vị trí \(s \in \mathbb{Z}\) và với mỗi bước di chuyển, nó nhảy một khoảng cách \(z \in \mathbb{Z}\) (nếu \(z>0\) , nó nhảy sang phải; ngược lại, sang trái). \(z\) không đổi cho mỗi lần nhảy. Việc bắt con ếch liên quan đến việc xác định một vị trí số nguyên. Cả \(z\) và \(s\) đều không được biết. Chúng ta sẽ chứng minh rằng có một quy trình luôn cho phép chúng ta 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.