Бака сан сызыгында секирип жүрөт жана максат - аны кармоо. Секирүү жана кармоо кезектешип жүргүзүлөт. Бака \(s \in \mathbb{Z}\) абалынан башталат жана ар бир жүрүш менен \(z \in \mathbb{Z}\) аралыкка секирет (эгер \(z>0\) болсо, ал оңго, болбосо солго секирет). \(z\) ар бир секирүү үчүн бирдей. Баканы кармоо бүтүн сандын позициясын көрсөтүүнү камтыйт. \(z\) да, \(s\) да белгисиз. Баканы кармоого ар дайым мүмкүндүк берген процедура бар экенин көрсөтөбүз.
Биринчи кезекте, \(a_1 = s\) жана \(a_{n+1} = a_n + z = s + n \cdot z\) менен \(s,z \in \mathbb{Z}\) .
Биз азыр тандайбыз
$$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 ) $$
ар бир натуралдык санга бүтүндөй сандардын сандык кортежин (так) берген функция катары. Бул функцияны тандоо \(f(n) = (-1)^n \left \lfloor \frac{n}{2} \right \rfloor\) , \(\mathbb{N}\) функциялары аркылуу жүргүзүлөт \(\mathbb{Z}\) жана \(g(2^kr) = (k+1, \frac{r+1}{2})\) , ал \(\mathbb{N}\) боюнча \(\mathbb{N}^2\) карта биективдүү, жүйөлүү.
Азыр биз \(h\) ( \(h\) динамикалык бурчтугун көрсөтөбүз, бирок бул касиеттин бизге кереги жок).
\((x,y) = (2^{k_1} r_1, 2^{k_2} r_2) \in\mathbb{Z}^2\) . Бирок кийин
$$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).$$
Демек: \(\forall (s,z) \in \mathbb{Z}^2 \, \exists \, m \in \mathbb{N}\) менен \(h(m) = (x_m,y_m) = (s, z)\) .
Мисалы, биздин кезегибиз \(n = 88\) , \(h(88)=(2,3)\) эсептейбиз жана \(2 + 88 \cdot 3 = 266\) позициясы катары тандайбыз.
Андан кийин \(m\) \(x_m + m \cdot y_m = s + m \cdot z = a_m\) менен \(x_m + m \cdot y_m = s + m \cdot z = a_m\) соң тандоо бакага түшөт.
\(h\) дан тышкары, Кантордун жупташуу функциясы же биективдүү спираль сыяктуу көптөгөн башка функциялар мүмкүн.
Бул жерде JavaScript'те жөнөкөй ишке ашыруу:
See the Pen catch the frog by David Vielhuber (@vielhuber) on CodePen.