Question

你站在点 $100$ 100在实线上。你有一份文件必须到达点 $0$ 0尽快。您唯一可用的两个信使会感到困惑，可能会向后走而不是向前走，如下所述。

你给每个快递员一份文件。然后，在每个时间步骤，你告诉他们要前进多少步，可以是任意整数 ${0, 1, 2, 3}$ \{0, 1, 2, 3\}。然后，会发生以下两种情况之一（其中 $s_{A}$ s_A你告诉快递员的号码是多少 $A$ A和 $s_{B}$ s_B你告诉快递员的号码 $B$ B)：

快递员A搬家 $s_{A}$ s_A向前迈进（朝着 $0$ 0）和快递员B移动 $s_{B}$ s_B向后退；
快递员A搬家 $s_{A}$ s_A后退，快递员 B 移动 $s_{B}$ s_B向前迈进。

您无法提前知道哪种选择会发生；这取决于信使不断变化的心情。

问题：你能确保至少有一名快递员最终到达目的地吗？ $0$ 0? 如果是的话，在最坏的情况下，您需要多少时间步骤？

_{以下是游戏如何展开的一个例子。初始状态是 $(A = 100, B = 100)$ (A=100, B=100). 您发送 $(3, 3)$ (3,3)；假设选项 1 发生，因此 A 向前走，B 向后走。那么下一个状态是 $(A = 97, B = 103)$ (A=97, B=103). 在下一个时间步骤中，你发送 $(2, 3)$ (2,3)。如果选项 1 发生，下一个状态是 $(A = 95, B = 106)$ (A=95, B=106)；否则，下一个状态是 $(A = 99, B = 100)$ (A=99, B=100)。}

编辑：要送达文件，只要其中一名快递员经过点 0 附近，甚至无需停留即可。因此，如果状态为 (1,1)，并且快递员 A 向前移动 2 步，您就赢了。

如果信使 A 在 1 处并向前移动 2 步，会发生什么情况？如果之后信使 A 再次向前移动 2 步，会发生什么情况？ — 
很有趣。不清楚“最坏情况”会是什么样子。最初，我以为可能是“信使同意最大化他们的头寸总和”，但那行不通……只需给出指令 $(1, 3)$ (1,3)反复。所以也许它“更接近于 $0$ 0总是后退”……也许这就是他们之间的距离？距离有多近 $0$ 0你能保证找到一个男人吗？ — 
如果我没看错，条款里说的这些条款是不能保证送货上门的。快递员可能会碰巧（或配合）总是选择离自己最近的快递员 $0$ 0远离 $0$ 0，如果我是对的，我会将其作为答案发布。 — 
@EthanBolker 我觉得这不管用。发送 $(2, 2)$ (2, 2)进而 $(1, 3)$ (1, 3). 职位将为 $(100, 100) \to (98, 102) \to (99, 99)$ (100, 100) \to (98, 102) \to (99, 99). 重复直到消息被传递。 — 
@Will.Octagon.Gibson 在这种情况下你仍然获胜（即使不停止，通过 0 也足够了）。 —

Answer 1

我相信信使采取的以下策略应该可以阻止消息到达。

显然，只有 $16$ 16可能的消息。计算某条消息被发送的次数，取模 $2$ 2。如果一条消息出现两次，第二次则执行与第一次相反的动作。这样，在任何时间点，两位信使最多移动 $4 \cdot (0 + 1 + 2 + 3) = 4 \cdot 6 = 24$ 4 \cdot (0 + 1 + 2 + 3) = 4 \cdot 6 = 24牌向前。这表明对于任何起始牌，答案都是否定的 $\geq 25$ \geq 25。

如果您选择 16 个中的一些从选项 1 开始，并且选择一些从选项 2 开始，则可以进一步缩小界限。 — 
@frodoskywalker 没错。如果您愿意，您可以添加更好的界限作为编辑建议。 — 
@Smiley1000 我本来打算这么做，但最后还是把它写成了自己的答案。不过我很确定这仍然可以改进 —

Answer 2

我确实相信，没有获胜策略。

经过一番思考（并且没有什么好的直觉）后，我尝试用 Python 中的一个小程序来测试我的直觉。

该程序基于以下内容：您可以迭代地计算获胜点集：

从位置 (x,y) 开始，如果存在选项 1 或 2 导致获胜位置的玩法，则将 (x,y) 添加到获胜位置集合

从计算完成时起，情况就是如此。如果您处于获胜位置，则可以采取允许该位置添加到获胜集合的策略。此策略为您提供了一种降低位置等级的策略（其中等级是我们添加位置的迭代）。

在这组获胜位置之外，对于您选择的任何数字，信使都可以表现得让您停留在获胜位置之外（通过构造），因此它们永远不会达到 0。

假设我的编程是正确的，那么具有获胜策略的位置集是：

{(-11, 2), (4, 9), (1, -15), (1, -6), (11, -4), (-8, 1), (-4, -8), (-4, 1), (7, 1), (12, -3), (-12, -3), (4, -7), (-4, 10), (-11, 4), ( 4、 2), (1, -13), (3, 6), (8, 2), (0, -2), (0, -1), (11, -1), (11, -2), (-8, -6), (-8, 3), (15, -1), (-4, -6), (7, -6), (-4, 3), (7, 3), (-11, -3), (-16, 1), (4, -5), (8, -5), (3, 8), (8, 4), (-5, 4), (0, 0), (-8, -4), (-8, 5), (-4, -4), (7, -4), (-4, 5), (7, 5), ( -12, 1), (3, 1), (14, 1), (8, -3), (3, 10), (-5, 6), (0, 2), (11, 2), (-8, -1), (-8, -2), (-4, -11), (-4, -1), (-4, -2), (7, -1), (7, -2), (-4, 7), (4, -10), (7, 7), (-12, 3), (3, -6), (3, 3), (3, 12), (-5, 8), (11, 4), (-4, -9), (-16, -1), (2, 13), (-4, 9), (3, -4), (-5, -8), (3, 5), (-5, 1), (0, -3), (11, -3), (-8, 2), (10, 1), (- 4, -7), (7, -7), (2, 6), (-4, 2), (7, 2), (-12, -1), (-12, -2), (3 ,-11), (3, -1), (3, -2), (14, -1), (-5, -6), (14, -2), (3, 7), (-5, 3), ( -8, -5), (10, 3), (-4, -5), (7, -5), (2, 8), (-4, 4), (7, 4), (3, -9), (6, 8), (3, 0), (-5, -4), (-1, 13), (3, 9), (-2, 13), (-5, 5), (10, -4), (2, 1), (-9, 1), (-4, -3), (7, -3), (2, 10), (-12, 2) , (3, -7), (-1, 6), (-2, 6), (3, 2), (14, 2), (-5, -1), (-5, -2), (-1, 15), (3, 11), (-5, 7), (10, -1), (10, -2), (2, -6), (-4, -10), (2, 3) , (-9, 3), (2, 12), (6, 3), (3, -5), (-1, 8), (-2, 8), (3, 4), (-5) , -9), (-1, 17), (-5, 9), (2, -13), (2, -4), (-9, -4), (2, 5), (-9, 5), (-17, 1), (2, 14), (6, -4), (6, 5), (3, -12), (-1, 1), (-2, 1), (3, -3), (-13, 1), (-1, 10), (-2, 10), (-5, -7), (-5, 2), (2, -11), (10, 2), (9, 4), (2, -1), (2, -2), (-9, -1), (-9, -2), ( 2, 7), (6, -1), (6, -2), (-1, -6), (-2, -6), (3, -10), (6, 7), (- 1, 3), (-2, 3), (-5, -5), (-1, 12), (-2, 12), (17, 1), (9, -3), (2, -9), (5, 8), (10, 4), (-6, 8), (2, 0), (2, 9), (-1, -13), (-2, -13) , (-1, -4), (-2, -4), (3, -8), (-1, 5), (-2, 5), (-10, 1), (-5, – 3), (-1, 14), (-2, 14), (5, 1), (-6, 1), (10, -3), (2, -7), (-3, 6), (2 , 2), (-9, 2), (-17, -1), (2, 11), (6, -7), (-1, -11), (-2, -11), (6 , 2), (-1, -1), (-1, -2), (-2, -1), (-2, -2), (-13, -1), (-1, 7), (-2, 7), (1, 15), (-10, 3), (-13, -2), (-1, 16), (-6, -6), (5, 3) ), (-6, 3), (2, -14), (9, 1), (2, -5), (-9, -5), (-3, 8), (2, 4), (-9, 4), (13, 1), (6, -5), (1, 8), (-1, -9), (6, 4), (-2, -9), (- 1, 0), (-2, 0), (1, 17), (-10, -4), (-1, 9), (-2, 9), (5, -4), (-6 , -4), (17, -1), (5, 5), (-6, 5), (2, -12), (-3, 1), (9, 3), (2, -3), (-9, -3), (-14, 1), (-3, 10), (-1, -16), (6, -3), (-1, -7), ( -2, -7), (1, 10), (6, 6), (-7, 6), (-2, 2), (-1, 2), (-13, 2), (-10 , -1), (-10, -2), (-1, 11), (-2, 11), (5, -1), (-6, -1), (5, -2), (- 6, -2), (-3, -6), (2, -10), (5, 7), (9, -4), (-3, 3), (-6, 7), (9 , 5), (-3, 12), (1, 3), (-1, -14), (-2, -14), (16, 1), (-1, -5), (-2, -5), (1, 12), (-1, 4), (-2, 4), (5, -9), (-3, -4), (9, -1), (2, -8), (9, -2), (5, 9), (-3, 5), (4, 11), (1, -4), (13, -1), (13, -2), (6, -8), (1, 5), (-1, -12), (6, 1), (-7, 1), (-2, -12), (-1, -3), (-2 , -3), (1, 14), (-10, 2), (5, -7), (-6, -7), (-3, -11), (-6, 2), (5 , 2), (4, 4), (-3, -1), (-3, -2), (-14, -1), (-14, -2), (-3,7), (1, -11), (1, -1), (1, -2), (6, -6), (-7, -6), (1, 7), (-1, – 10), (-2, -10), (-7, 3), (1, 16), (-10, 4), (12, 1), (5, -5), (4, -3) , (-6, -5), (-3, -9), (5, 4), (-6, 4), (4, 6), (-3, 0), (9, 2), ( -3, 9), (1, -9), (8, 6), (1, 0), (13, 2), (-1, -17), (-7, -4), (16, -1), (-1, -8), (1, 9), (-2, -8), (-7, 5), (-15, 1), (-10, -3), (- 11、 1), (12, 3), (5, -3), (-6, -3), (-3, -7), (9, -5), (5, 6), (-6, 6 ), (4, 8), (-3, 2), (1, -16), (-14, 2), (-3, 11), (1, -7), (1, 2), ( -1, -15), (-7, -1), (-7, -2), (1, 11), (-7, 7), (4, -9), (4, -8), (-11, 3), (4, 1), (-3, -5), (4, 10), (-3, 4), (1, -14), (8, 1), (1, -5), (1, 4), (1, 13), (12, -1), (12, -2), (5, -8), (4, -6), (-6, -8) ), (-3, -12), (-4, 11), (-11, -4), (4, 3), (-3, -3), (8, -6), (1, -12) , (8, 3), (1, -3), (-7, -7), (1, 6), (-7, 2), (-8, 4), (-15, -1), (-11, -1), (-11, -2), (5, -6), (4, -4), (-3, -10), (4, 5), (8, -4) , (1, -10), (8, 5), (0, 1), (11, 1), (-7, -5), (-8, -3), (-7, 4), ( -8, 6), (15, 1), (-4, 6), (7, 6), (12, 2), (4, -11), (4, -1), (4, -2) ), (-3, -8), (4, 7), (1, -17), (8, -1), (8, -2), (1, -8), (1, 1), (0 , 3), (11, 3), (-7, -3), (-4, 8)}

代码：

play = []


for i in range(4):
    for j in range(4):
        play += [(i,j)] 
        play += [(-i,-j)] 
        play += [(i,-j)] 
        play += [(-i,j)] 
  
winning_positions= set(play)

def sign(x):
    if x>0:
        return 1
    elif x<0:
        return -1
    else:
        return 0

new = True
while new:
    new = False
    ng = set()
    for (a,b) in winning_positions:
        for (e,f) in play:
            (x,y)=(a+e,b+f)
            if sign(x)*sign(e) >0:
                valid = sign(y)*sign(f)<=0
            elif sign(x)*sign(e) <0:
                valid = sign(y)*sign(f)>=0
            else:
                valid = True
    
            if valid and x*y != 0:
                if not (x,y) in winning_positions:
                    if (a+2*e,b+2*f) in winning_positions:
                        ng.add((x,y))
                    if a+2*e==0:
                        ng.add((x,y))
                    if b+2*f==0:
                        ng.add((x,y))
            
    winning_positions=winning_positions.union(ng)
    new = (len(ng)>0)

print(winning_positions)```

我认为你有一个误解：这只能发生，要么 $A$ A向前迈进， $B$ B向后退，或 $A$ A向后退 $B$ B向前迈进。因此，在您的四行“play += …”中，有两行是不允许的。 — 
是的，这就是我理解和实现的。我使用有效变量检查游戏是否有效。处理负数有点复杂。在我的实现中，A 或 B 都朝着 0 迈进（如果其中一个为负数，则两者都可以增加） — 
好的，也许我应该更仔细地阅读你的代码 ^^ 我注意到的另一件事是，原始问题中有一个歧义：如果一个信使越过零点，这算赢吗？例如从 $2$ 2到 $- 1$ -1。无论如何，我认为你的方法是正确的。+1 — 
我认为只有零分才是胜利。超过零分只是改变了我前进的方向。 —

Answer 3

基于 smiley1000 的优秀解决方案，信使可以在其起点周围维持更紧密的区域。

Smiley1000 正确地指出，我们可以给信使总共 16 条指令。如果每次他们收到特定指令时都交替选择他们选择的选项，那么他们都不会在 0 方向上偏离超过 24 个空格。如果他们选择对每个指令的初始响应，我们可以将其减少到 7 个空格：

操作说明	初始响应	最大(A)	最大值(B)
（0,0）	一个	0	0
（0,1）	一个	0	0
（0,2）	一个	0	0
（0,3）	一个	0	0
（1,0）	乙	0	0
（1,1）	一个	1	0
（1,2）	一个	1	0
（1,3）	一个	1	0
（2,0）	乙	0	0
（2,1）	乙	0	1
（2,2）	一个	2	0
（2,3）	一个	2	0
（3,0）	乙	0	0
（3,1）	乙	0	1
（3,2）	乙	0	2
（3,3）	乙	0	3

该表显示了指令、第一次收到此消息时将向位置 0 移动的信使，以及每个信使可以通过此消息向零移动的最大距离。每个 max() 列中的总数为 7，表示如果我们从大于 7 的任何位置开始，此策略就会失败。

有趣！你有没有发现一个简单的方法可以将此概括为每条可能的消息都处于 ${0, \dots, k}$ \{0,\ldots,k\}？ — 
您可以根据哪个信使的指令较小来划分集合 – 让它们朝 0 迈进，然后对于指令相等的情况，对它们进行划分，使得两个信使从它们的单次迭代中向前/向后采取相同数量的步数。对于所有 k = 4n + 1 或 k = 4n + 2，这不会平等划分。我怀疑，但不知道，对于所有 k = 4n + 3 和 k = 4n，它会平等划分。 — 
假设我们总是可以分割 {n,n} 条指令，使得最坏的情况下，一个信使在初始指令集上比另一个信使更近一步，那么我们可以保证将这些信使移向 0 的最大距离将是 ceiling(kth 三角数/2) + ((k-1)th 金字塔数) —

Answer 4

注意：以下答案假设“困惑”的快递员随机选择方向。

问题：你能确保至少有一个信使最终到达点 0 吗？

是的，几乎肯定（即，我的意思是从数学/概率意义上来说

在每个时间步骤，告诉他们移动 1 步。两个信使现在都在进行，将无限次跨越任意边界（即，包括起点 + 100）。

如果是这样，在最坏的情况下，您需要多少时间步骤？

最坏的情况是无限的。正如，任何序列都可以在两个方向上无限重复，从而阻止所有进展（对于我的序列，仅仅交替方向就足以触发此问题）。

组合学 – 如何使用两个困惑的信使发送文件？ – 数学

最佳答案
4

组合学 – 如何使用两个困惑的信使发送文件？ – 数学

最佳答案 4

最佳答案
4