Żaba przeskakuje na osi liczbowej i próbujesz ją złapać. Skakanie i łapanie zawsze występują naprzemiennie. Żaba zaczyna się w pozycji \(s \in \mathbb{Z}\) iz każdym ruchem przeskakuje na odległość \(z \in \mathbb{Z}\) (jeśli \(z>0\) , skacze w prawo, w przeciwnym razie w lewo). \(z\) jest takie samo dla każdego skoku. Przyciąganie polega na określeniu pozycji całkowitej. Nie znamy ani \(z\) ani \(s\) . Pokazujemy, że zawsze można złapać żabę.
Przede wszystkim \(a_1 = s\) i \(a_{n+1} = a_n + z = s + n \cdot z\) z \(s,z \in \mathbb{Z}\) .
Wybieramy teraz
$$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 ) $$
jako funkcja, która przypisuje (dokładnie) krotkę liczb całkowitych do każdej liczby naturalnej. Wybór tej funkcji odbywa się poprzez funkcje \(f(n) = (-1)^n \left \lfloor \frac{n}{2} \right \rfloor\) , \(\mathbb{N}\) on \(\mathbb{Z}\) i \(g(2^kr) = (k+1, \frac{r+1}{2})\) , które \(\mathbb{N}\) włączone \(\mathbb{N}^2\) mapa bijektywnie, zmotywowana.
Teraz pokazujemy, że suriektywność \(h\) ( \(h\) jest również iniekcyjna, ale nie potrzebujemy tej właściwości).
Niech \((x,y) = (2^{k_1} r_1, 2^{k_2} r_2) \in\mathbb{Z}^2\) . Ale wtedy
$$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).$$
Stąd: \(\forall (s,z) \in \mathbb{Z}^2 \, \exists \, m \in \mathbb{N}\) with \(h(m) = (x_m,y_m) = (s, z)\) .
Na przykład, jeśli nadeszła nasza kolej, aby przejść o \(n = 88\) , obliczamy \(h(88)=(2,3)\) i wybieramy pozycję \(2 + 88 \cdot 3 = 266\) .
Następnie po dokładnie \(m\) ruchach z \(x_m + m \cdot y_m = s + m \cdot z = a_m\) wybór należy do żaby.
Oprócz \(h\) , możliwych jest wiele innych funkcji, takich jak funkcja parowania Cantora lub spirala bijektywna .
Oto prosta implementacja w JavaScript:
See the Pen catch the frog by David Vielhuber (@vielhuber) on CodePen.