Ловить лягушек

Лягушка прыгает по числовой прямой, и вы пытаетесь ее поймать. Прыжки и ловля всегда чередуются. Лягушка начинается в позиции \(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.

Назад