捉青蛙

一只青蛙在数字线上跳来跳去,试图捉住它。 跳跃和捕捉总是交替发生的。 青蛙开始于位置\(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}\) with \(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.

背部