Question

天气这么好，你决定在附近一条很大的环形路上悠闲地散步。你知道这个环形路的半径，但它太大了，你无法仅凭肉眼分辨出里面和外面。在迷路了好一会儿之后，你终于想回家了。但是出口在哪里呢？你记得你只能在一个点离开这条路。而且，这个点很容易错过——光是走过是不行的，你需要在离它很近的地方停下来片刻才能注意到。现在，问题是你的方向感极差。即使只停了一秒钟，你也会立刻忘记自己是从哪个方向来的！因此，简单地朝同一个方向走一小步对你来说不是一个选择。那么，你该如何出去呢？

您最终能想出一个策略来找到出口吗？

（注：这是一个数学难题，而不是一个横向思维难题。对随意术语的准确解释应该是：

该轨道是一个已知半径的完美圆（欧几里得圆）。
你是该圆上某处的点，但你不知道其具体位置。
出口是圆上的一小段。你不知道它有多小，所以你的策略应该适用于所有可能的尺寸。
在任何时间点，您都可以在轨道上朝一个方向移动任意（完全精确）的距离，但您无法判断您的运动是顺时针还是逆时针。
当且仅当您的某些动作导致您在出口处停下来时，您才获胜。

此外，您的策略应该保证您最终在每一种可能的情况下都能摆脱困境——仅仅花费大量的时间（比如从某种概率意义上来说）是不够的。）

如果这对你来说太简单了，这里还有一个小奖励问题：

假设出口也只是一个点（而不是一个线段）。你能确定你有机会可靠逃脱的确切起始位置吗？（这还涉及表明其他点不能通过任何策略赢得，而不仅仅是你想出的策略。）

我希望你喜欢这个小谜题，玩得开心！:)

这个问题太难了！我几乎肯定得四处走走，然后祈祷能有好结果。 — 
我将最后一段解释为该策略必须适用于所有情况，而不是对抗性选择的方向？仅仅以概率 1 工作（假设独立采样的方向）是不够的，对吗？我最初以不同的方式解释了那段话，花了一些时间想出了一个解决方案，归根结底就是朝着同一个方向迈出很小的步伐。 — 
@shapewarriort 是的，该策略应该适用于所有情况，即从所有位置和每个选定方向序列（特别是对于对抗性选择的方向，但无需强加意图）。例如，使用有关 rot13(enaqbz jnyxf) 的一些基本事实，不难看出 rot13(jnyxvat gur fnzr (veengvbany) yratgu ng rirel ghea) 让您以 1 的概率从每个位置退出，但这还不够 🙂 —

Accepted Answer

对于非零段大小：

以下递归“二分搜索”式方法适用于任意小的出口尺寸。（每次移动后检查出口）：

搜索 1：

– 绕圆一半。

（这将检查圆周上等距分布的两个点。）

搜索 2：

– 执行搜索 1。-

绕 1/4 圈（无论哪种方式）。-

重复搜索 1。

（这将检查圆周上等距分布的四个点。）

搜索 3：

– 执行搜索 2。-

绕 1/8 圈（仍然无论哪种方式）。-

重复搜索 2。

（这将检查圆周上等距分布的八个点。）

搜索 4：

– 执行搜索 3。-

绕 1/16 圈。-

重复搜索 3。

（这将检查圆周上等距分布的十六个点。）

…

搜索 N：

– 搜索 N-1。-

绕圆 1/(2^N)。-

重复搜索 N-1

（检查圆周上等距分布的 2^N 个点。）

…

对于零段大小的情况：

只有当从起点到圆的距离是分母为 2 的幂的有理分数时，上述策略才能找到出口。

对于均匀分布的出口，这大约是 0% 的时间。

我看不出有任何方法可以提高这个数字。

速度很快，干得好！（这基本上也是预期的策略。）如果你有兴趣，祝你在剩下的奖金部分好运 🙂 —

Answer 2

对于单点退出，没有比@fljx 的答案更好的了。

为了简化符号，我们使用一个周长为 1 的圆，假设出口在 0，而你不知道自己在哪里。请注意，对于这个问题，位置 x+1 与位置 x 相同（每个位置有多个数字）。让 $B$ \mathbb{B}（对于二进制分数）是形式为 $\frac{k}{2^{n}}$ \frac{k}{2^n}. 如果你正在 $B$ \mathbb{B}，您可以使用@fljx 的回答中描述的策略来逃脱。

另一方面，如果你不在 $B$ \mathbb{B}，那么你不能保证去 $B$ \mathbb{B}：假设你位于 $x$ x并选择步行距离 $d$ d，那么你想要 $x + d = y_{1}$ x+d = y_1和 $x - d = y_{2}$ x-d = y_2和 $y_{1}$ y_1和 $y_{2}$ y_2在 $B$ \mathbb{B}，但随后 $x = \frac{y_{1} + y_{2}}{2}$ x = \frac{y_1 + y_2}{2}位于 $B$ \mathbb{B}，矛盾。所以如果你从 $B$ \mathbb{B}，和 $B$ \mathbb{B}正是你能保证获胜的位置集合。

要小心，因为

如果在任何时候你移动的距离不在 $B$ \mathbb{B}，至少有一个方向会带你走出 $B$ \mathbb{B}你就不能再保证获胜了。

Answer 3

可能需要一些时间，但我们可以出去。

假设圆的周长 $1$ 1. 策略是选择任意无理数 $X$ X，说 $\sqrt{2}$ \sqrt{2}，然后以该数字的二进制倍数递增的方式行走。从你的起点开始，步行距离 $X$ X， $2 X$ 2X， $4 X$ 4X， $8 X$ 8X等等。这种马丁格尔策略确保我们不会陷入向后移动到已经访问过的点的循环，并且 $X$ X确保我们在沿着合理长度的轨道向前移动时也不会重新访问点。只要我们愿意，我们就可以继续我们的策略，继续访问圆上的新点，确保我们最终能找到出口。

正如评论中指出的那样，访问无数个唯一点并不能证明我们找到了出口，例如，如果我们“仅”检查一个连续半圆上的无限个点。但如果我们的策略做到了这一点，那就意味着该策略在较小的圆上也能奏效，而且如果我们一开始就将步长加倍，我们就会成功。然而，我们的前提是，我们对非合理步长的选择根本不取决于轨道的大小。

嗯，虽然你肯定不会用这个策略重复任何位置，但我不太清楚你的位置序列是否必须在圆圈内密集。事实上，我甚至不明白为什么你不能按照这个策略呆在圆圈的同一半边。你能详细说明一下吗？ — 
@TimSeifert 是的，我发布这篇文章后意识到了逻辑上的一些漏洞。访问无数个唯一点本身并不能保证这些点覆盖圆的所有任意小部分。我认为这样做是可行的，因为我们最终开始进行完整循环，并且无理步长模循环次数本身就是无理的，而二进制倍数只是不断将该“相位”推得越来越远，但我不太确定如何证明这一点。 — 
我认为你可以按照以下思路建立一个反例：把圆看作 $[0, 1] / (0 \sim 1)$ [0,1]/(0\sim 1)并选择一个二进制表示包含越来越多的 0 且被单个 1 打断的数字（显然是无理数）。乘以 $2^{n}$ 2^n然后具有将二进制表示向前移动的效果 $n$ n步骤。因此，每当你刚刚“推过”另一个 1 并等待一长串 0 时，你就可以朝着相同的方向走完所有的 0，朝着不同的方向走完接下来的 1…… — 
… 如果这段路程足够长，那么你将朝一个方向迈出几乎半圈的步伐，然后走回几乎起点，因此几乎没有净移动。我还没有完全弄清楚，但似乎只要让这些路程足够长，你就能将所有误差的总和限制在（比如说）1/6。因此，你的移动将完全保持在圆圈的 2/3 以内。 — 
（现在，选择某个特定值可能仍然会产生有效的策略，但这表明它并不适用于每个无理数。） —

数学 – 在环形轨道上迷路 – 令人费解的

最佳答案
3

数学 – 在环形轨道上迷路 – 令人费解的

最佳答案 3

最佳答案
3