カエルを捕まえる

カエルがナンバーラインを飛び回り、あなたはそれを捕まえようとします。 ジャンプとキャッチは常に交互に行われます。 カエルは位置\(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}\)介して行われます。 on \(\mathbb{Z}\) and \(g(2^kr) = (k+1, \frac{r+1}{2})\) 、which \(\mathbb{N}\) on \(\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\)に加えて、 Cantorのペアリング関数バイジェクティブスパイラルなどの他の多くの関数可能です。

これがJavaScriptでの簡単な実装です:

See the Pen catch the frog by David Vielhuber (@vielhuber) on CodePen.

バック