警察和小偷

uk702

在一个开放平面上，有2个警察和1个小偷，3者初始位置不重合，假如小偷跑的速度比警察快，显然，只要小偷总是按两个警察连线的垂直方向跑，则警察永远也追不上小偷。
1）在开放平面上，假设有 n 个警察和 1 个小偷，只要小偷跑得比警察快，小偷是否总有一种策略不被抓住？
2）现将警察和小偷的活动范围都限制为单位圆内，警察还能否抓住小偷？

mathe

如果我们总是将警察和小偷看出质点（无穷小），那么小偷总是可以先充分接近某一个警察，然后我们可以仅查看充分小的范围之内充分短时间的情况（这时可以想象把整个平面以小偷为中心放大充分大的倍数的局面），这时小偷和警察是一对一的，于是小偷可以绕过警察。
而实际情况小偷和警察都不是距离，两人接近到某一种程度（比如距离小于0.5米）警察就可以逮住小偷了，所以只要有足够警察就可以抓住小偷了（比如极端情况每两个警察之间距离不超过0.5米，他们可以手拉手围住小偷。

uk702

mathe 发表于 2021-4-14 08:48
如果我们总是将警察和小偷看出质点（无穷小），那么小偷总是可以先充分接近某一个警察，然后我们可以仅查看 ...

我对 mathe 老大的解答其实还是有疑问的。现仍将各个警察和小偷都视作质点，我们说两个警察的情况下警察一定抓不到小偷，因为我们总能找到一个方向并且让小偷跑上一个“微距”从而远离所有的警察。

1）现假设有 3 个警察，呈正三角形分布，小偷位于正三角形的中心，每个警察和小偷的距离都是 1 米，这时，小偷能否找到一个方向并跑上一个“微距”，从而远离任何一个警察？

2）再假设有 6 个警察，呈正六边形分布，小偷位于正六边形的中心，每个警察和小偷的距离都是 1 米，这时，小偷能否找到一个方向并跑上一个“微距”，从而远离任何一个警察？或者，这时小偷能否跑出警察的包围？如果小偷的跑动距离大于某个警察，个人觉得并无法保证没有某个警察抓住小偷，龟免赛跑，没说免子之所以追上乌龟，是因为乌龟有长度呀。（比如说12个警察围成上一圈，小偷仅仅是比警察快上个0.1，小偷还能跑出去吗？）

3）更多的警察呢？

uk702

mathe 发表于 2021-4-14 08:48
如果我们总是将警察和小偷看出质点（无穷小），那么小偷总是可以先充分接近某一个警察，然后我们可以仅查看 ...

在一个开放平面上，将警察和小偷都视作质点，如果有6个警察将小偷围住，估计是能将小偷抓住的。
假设小偷正位于单位圆周的圆心上，而 6 个警察则在单位圆周上均匀分布。

1）现假设小偷以某个方向定向匀速跑动，则只需移动某个警察，堵在该方向与圆周的交点位置上，就能将小偷抓住。

2）假设小偷以某个方向定向匀速跑动，而移动某个警察堵在该方向与圆周的交点位置上，而小偷定向跑了一小段位置后，开始以 45° 转向。

这时如果只是一个警察来堵的话，这个警察要堵住这个小偷，他的最小移动距离和小偷的跑动距离正好相等，但由于小偷的速度比警察快，因此，警察是堵不住小偷的。

所以，当小偷定向跑动时，为了防止小偷中途变向，至少要三个警察同时来堵，一个警察堵在小偷跑动的正方向，另外两个警察堵住小偷两个 45° 转向的位置。这时，那怕小偷来个 90°转向，警察依旧能将小偷堵住。

3）为了防止小偷在跑动过程超过90°的转向，在小偷定向跑动时，其余的 n-3 个警察，以小偷为圆心向小偷靠拢，缩小包围圈。

mathe

1) 现假设小偷以某个方向定向匀速跑动，则只需移动某个警察，堵在该方向与圆周的交点位置上，就能将小偷抓住
========================
一个警察肯定是堵不住的，小偷在充分接近警察以后（比如和警察的距离为d),然后改为横向移动，知道和警察横向距离差超过d,在改回原方向向前冲刺警察就很难拦截了。当然这个描述还不够精准，但是给定速度比以后，我们是能够计算出一个确定的模型的。只要让d充分小，使得这时其他警察的距离相对d比例很大，就都可以忽略了。而小偷越过警察后就可以轻松调整回到原先起始的直线上。
所以唯一的问题是多个警察是否能够保持同步堵截的问题。但是感觉很难，主要问题是不管多少警察，都无法保持包围状态，小偷总是可以通过和前面多个警察充分接近的情况下使得看起来后面的警察都已经被完全甩开了而避免了被包围的状态。
其中为了能够堵截小偷，局部需要安排至少两个警察，但是在诱使部分警察向局部集中后，小偷可以通过快速平移来脱离这几个被局部集中的警察从而彻底抛开他们。当然这些分析都很不严格。

如果我们改为考虑n个警察将小偷堵在一个单位圆内，警察只能在圆周上移动，小偷的目标是逃离圆而不会被警察堵住，那么这个问题就相对比较容易分析了。考虑到小偷充分贴近圆周（距离小于圆周周长除以2n并乘上(d-1), d为两者速度的比例）并且沿着圆周快速移动时，如果我们局部放大以后，圆周和直线的区别已经很小了，由于警察不可能遍布圆周边界，小偷速度比警察快，总可以找到一处没有警察布防的边界穿越。

uk702

mathe 发表于 2021-4-15 08:27
1) 现假设小偷以某个方向定向匀速跑动，则只需移动某个警察，堵在该方向与圆周的交点位置上，就能将小偷抓 ...

个人认为在警察和小偷的行动都透明的情况下，可以做到不是所有警察不被小偷吸引到一个局部的情况。

n+3个警察的情况下，大体上，当小偷接近圆周内界时，我们可以用3个警察，一个守住小偷行动方向的正对面，另两个警察守住小偷行动方向的两个 45 度转向。（严格来说，3 个警察不够，但 4 个或 5 个警察应该就足够了）。

剩下的 n 个警察，只要不承担那 3 个警察之一的角色，则始终守住自己的一亩三分田，不扎堆。

uk702

详细见如图的分析。

mathe

比如小偷速度是警察的1.1倍，小偷可以基本上认定一个方向垂直向前跑，但是有时候可以做一小部分水平方向移动，但是要保证水平方向移动的距离不超过垂直方向移动距离的0.1倍，在这种运动模式下，任意一个被小偷甩在身后的警察将再也没有机会追上小偷。用这种模式，小偷总可以一个一个的把警察甩在身后，让身前的警察越来越少，知道最后没有警察而逃之夭夭。
比如现在身前有k个警察正在迫近，身后的最后一个被甩开警察离他距离为d, 那么小偷总可以在离前面一个警察距离不超过d/100时开始水平向右，其中目标是水平移动d/11,垂直移动d/100，使得左侧和前方所有警察被甩开。当然在这个移动过程中，有可能会提前遇到部分右前方的警察，这时为了躲避这些右前方遇到的第一个警察，他可以通过使用更低分辨率，比如直到和这个警察距离小于d/10000时才开始躲避（从向右改为向左等，那么自然设定的目标改为垂直向前移动d/110,再水平向右移动d/10000躲开这个警察），再躲过这个右前方的警察以后，继续补充前面水平移动d/11和垂直移动d/100的未完成部分（同样水平方向优先完成）。
经过这样一次又一次的躲闪，前面的警察会越来越少，最终可以成功逃脱

uk702

mathe 发表于 2021-4-15 15:38
比如小偷速度是警察的1.1倍，小偷可以基本上认定一个方向垂直向前跑，但是有时候可以做一小部分水平方向移 ...

好，接受！

7# 的错误在于，当警察 A 堵在 P 正前方，但当 P 向 PI 方向移动一小距离，再沿平行于 AP 的方向向前跑，这时，由于小偷的速度是 A 的 1.1 倍，A是无法跑到 P 的正前方的，警察 B （及其他警察）更无法跑去补位。这样，这时没有警察能堵在 P 的正前方。

风云剑

如果警察只能在圆周上，小偷一直贴近圆周内缘跑，似乎总是能找到机会逃脱。
小偷比警察快，那么甩掉的警察就不用考虑了，只需考虑前方迎面过来的，而总有一个时刻，警察在小偷身旁，再往后又可以甩掉了，然后一个转弯就可以逃脱了吧。

警察不限于圆周的情况，比较复杂，关键就在于是否可能出现两个以上警察离小偷的距离一直相同，如果存在这种策略，貌似是可以抓到的。