Бака сан сызыгы боюнча секирип, сиз аны кармаганга аракет кыласыз. Секирүү жана кармоо ар дайым алмашып турат. Бака \(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.