Жаба стрибає по цифровій лінії, і ви намагаєтеся її зловити. Стрибки та лови завжди чергуються. Жаба починається з положення \(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\) вибір падає на жабу.
На додаток до \(h\) , можливо багато інших функцій, таких як спарювальна функція Кантора або бієктивна спіраль .
Ось проста реалізація в JavaScript:
See the Pen catch the frog by David Vielhuber (@vielhuber) on CodePen.