Here is an interesting problem that I came across on this site:
The Robot Weightlifting World Championship was such a huge success that the organisers have hired you to help design its sequel: a Robot Tug-of-War Competition!
I managed to come up with the following program after experimentation with different starting values.In each one-on-one matchup, two robots are tied together with a rope. The centre 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 -1. Each pull moves the marker a uniformly random draw from [0, 1] towards the pulling robot. If the marker first leaves the interval [‑½, ½] past ½, the first robot wins. If instead it first leaves the interval past -½, the second robot wins.
However, the organisers 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!
Figure 1: source |
Figure 2: permalink |
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) = \text{ p(Player 1 wins at a starting position of } x)$$The symmetry of the game implies $$ \begin{align} f(x) &= \text{ p(Player 1 wins on first move) } + \int_x^{½} \! \text{p(Player 2 wins at position }(-y)) \text{ d}y \\
&= (½ + x) + \int_x^{½}(1 - f(-y) ) \text{ d}y \end{align}$$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) \times (-1) = -f’(-x)= -f(x) \)
The general solution to this differential equation is
\(f(x) = A \sin(x) + B \cos(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
$$ \begin{align} A \sin(½) + B \cos(½) &= 1 \text{ and}\\
A \cos(0)- B \sin(0) &= A \sin(0) + B \cos(0) \end{align}$$The second equation implies \(A = B\), and the first equation then gives:$$\begin{align}A &= B\\ &= \frac{ 1} {\sin(½) + \cos(½)} \text{ and so}\\ f(x) &= \frac {\sin(x) + \cos(x)}{\sin(½) + \cos(½)} \end{align}$$Therefore the answer is the solution to: $$ \frac{\sin(x) + \cos(x)}{\sin(½) + \cos(½)} = ½ \text{ on }[-½,0]$$ A calculator can give this to the desired accuracy, -0.2850001…, or by using $$\sin(x) + \cos(x) = \sqrt{2}· \sin(x + \pi/4)$$we can exactly solve that the answer is$$ \arcsin \left (\frac{\sin(0.5+\frac{\pi}{4}}{2} \right )-\frac{\pi}{4}$$I don't fully understand this explanation but I'm exhausted from fine tuning the LaTeX so I'll return to it later.
No comments:
Post a Comment