机器人拔河比赛
Robot Tug-of-War
题目详情
机器人举重世界锦标赛非常成功，以至于组织者聘请您帮助设计其续集：机器人拔河比赛！
在每次一对一对决中，两个机器人被一根绳子绑在一起。绳子的中心有一个标记，它开始于地面上的位置 0 上方。然后机器人交替拉绳子。第一个机器人向 1 的正方向拉；第二个机器人向 -1 的负方向拉。每次拉动都会使标记向拉动机器人的方向移动 [0,1] 之间的均匀随机值。如果标记首先越过 ½ 离开区间 [‑½,½]，则第一个机器人获胜。如果它首先越过 -½ 离开该区间，则第二个机器人获胜。
然而，组织者很快注意到后上的机器人处于劣势。他们想通过将绳子上的标记的初始位置更改为某个负实数来限制第一个机器人。你的任务是计算出使每次对决成为机器人之间胜率 50-50 的比赛的标记位置。求这个位置精确到七位有效数字——机器人拔河比赛的完整性命悬一线！
The Robot Weightlifting World Championship was such a huge success that the organizers have hired you to help design its sequel: a Robot Tug-of-War Competition!
In each one-on-one matchup, two robots are tied together with a
rope. The center of the rope has a marker that begins above position 0
on the ground. The robots then alternate pulling on the rope. The
first robot pulls in the positive direction towards 1; the second
robot pulls in the negative direction towards
However, the organizers quickly noticed that the robot going second is at a disadvantage. They want to handicap the first robot by changing the initial position of the marker on the rope to be at some negative real number. Your job is to compute the position of the marker that makes each matchup a 50-50 competition between the robots. Find this position to seven significant digits—the integrity of the Robot Tug-of-War Competition hangs in the balance!
解析
为了找到使比赛公平的拔河起点，我们在 [-0.5,0.5] 上定义函数 f 如下：
f(x) =: Prob(玩家 1 在起点 x 处获胜)。
游戏的对称性意味着
f(x) = Prob(玩家 1 在第一步获胜) + ∫_{x}^{½} Prob(玩家 2 从位置 (-y) 开始获胜) dy
= (½ + x) + ∫_{x}^{½}(1 - f(-y))dy。
对等式求导并应用微积分基本定理，我们得到
f’(x) = 1 - (1 - f(-x)) = f(-x)。
再次求导并采用链式法则，然后代入上面的方程，我们得到
f’’(x) = f’(-x)·(-1) = -f’(-x) = -f(x)。这个微分方程的通解是
f(x) = Asin(x) + Bcos(x)。
我们需要两个边界条件来精确确定 f。首先，很明显我们必须有 f(½) = 1。其次，由上面的公式可知，f’(0) = f(0)
因此，Asin(½) + Bcos(½) = 1，并且 Acos(0) - B sin(0) = Asin(0) + Bcos(0)。
第二个方程意味着 A = B，然后第一个方程给出
A = B = 1/(sin(½) + cos(½))，所以 f(x) = (sin(x) + cos(x))/(sin(½) + cos(½))。
因此，答案是 (sin(x) + cos(x))/(sin(½) + cos(½)) = ½ 在 [-½,0] 上的解。计算器可以给出达到所需精度的值，即 -0.2850001…，或者通过使用
sin(x) + cos(x) = √(2)·sin(x + 𝜋/4)
我们可以精确解出答案为 arcsin(sin(½ + 𝜋/4)/2) - 𝜋/4。
恭喜本月成功找出进行公平的机器人拔河比赛所需答案的解谜者！
Original Explanation
In order to find the starting position of the tug-of-war to make a fair fight, we define the function f on [-0.5,0.5] as
f(x) =: Prob(Player 1 wins at a starting position of x).
The symmetry of the game implies
f(x) = Prob(Player 1 wins in the first move) + ∫x½ Prob(Player 2 wins starting at position (-y)) dy
= (½ + x) + ∫x½(1 - f(-y))dy.
Differentiating and applying the fundamental theorem of calculus, we get
f’(x) = 1 - (1 - f(-x)) = f(-x).
Differentiating again and employing the chain rule, and then substituting the equation above, we get
f’’(x) = f’(-x)·(-1) = -f’(-x) = -f(x). The general solution to this differential equation is
f(x) = Asin(x) + Bcos(x).
We need two boundary conditions to determine f exactly. First, it’s clear we must have f(½) = 1. Second, from the above formula, f’(0) = f(0)
Therefore, Asin(½) + Bcos(½) = 1, and Acos(0) - B sin(0) = Asin(0) + Bcos(0).
The second equation implies A = B, and the first equation then gives
A = B = 1/(sin(½) + cos(½)), so f(x) = (sin(x) + cos(x))/(sin(½) + cos(½)).
Therefore the answer is the solution to (sin(x) + cos(x))/(sin(½) + cos(½)) = ½ on [-½,0]. A calculator can give this to the desired accuracy, -0.2850001…, or by using that
sin(x) + cos(x) = √(2)·sin(x + 𝜋/4)
we can exactly solve that the answer is arcsin(sin(½ + 𝜋/4)/2) - 𝜋/4.
Congrats to this month’s solvers who successfully found the answer for running an honest robot tug-of-war!