Robot Tug-of-War
The field of play is the interval $[-\frac{1}{2},\frac{1}{2}]$. To simplify the maths later on, let's relabel this interval to be $[0,1]$; in other words, Robot 1 wins if the marker has position $x>1$ and loses if $x<0$.
We want to find the win probability function $w(x)$, which is the probability that Robot 1 wins eventually if it is currently its turn, and the marker is currently at location $x$. Once we find this function, we can solve for $x$ by setting $w(x)=\frac{1}{2}$.
Suppose the marker begins at $x_0$ and it's Robot 1's turn, who moves a distance $a$ which is uniformly distributed on $[0,1]$. Two things can happen:
- If $a\geq 1-x_0$, then Robot 1 immediately wins since the marker will pass the $x=1$ mark. This scenario occurs with probability $x_0$.
- If $a< 1-x_0$, then it does not win yet and the marker will now be at position $x_0 + a$. This scenario occurs with probability $1-x_0$.
In the second scenario, it will now be Robot 2's turn to move. We can describe Robot 2's eventual win probability with the same function $w(x)$. Given that the marker is currently at $x_0 + a$, Robot 2's eventual win chance will be $w\big(1-(x_0+a)\big)$. Equivalently, this means that Robot 1's eventual win chance prior to Robot 2's move is $\Big(1-w\big(1-(x_0+a)\big)\Big)$. As $a$ is a random variable distributed on $[0, (1-x_0)]$ in this scenario, then we can instead talk about Robot 1's expected eventual win chance as $$\mathbb{E}\Big(1-w\big(1-(x_0+a)\big)\Big)=1-\int_0^{1-x_0}\frac{w\big(1-(x_0+a)\big)}{1-x_0}da$$
We can now combine the two scenarios above into one equation for $w(x_0)$, using the scenarios' probabilities as weighting:
$$\begin{align*}w(x_0)&=x_0\cdot 1&&\text{(scenario 1)}\\&\;\;\;\;+(1-x_0)\cdot \mathbb{E}\Big(1-w\big(1-(x_0+a)\big)\Big)&&\text{(scenario 2)}\\&=x_0+(1-x_0)-(1-x_0)\int_0^{1-x_0}\frac{w\big(1-(x_0+a)\big)}{1-x_0}\cdot da\\&=1-\int_0^{1-x_0}w\big(1-(x_0+a)\big) da\\&=1-\int_0^{1-x_0}w(x)dx &&\text{(substituting $x=1-(x_0+a)$)}\end{align*}$$
Now we consider an infinitesmial addition $\delta$ to $x_0$.
$$\begin{align*}w(x_0+\delta)&=1-\int_0^{1-x_0-\delta}w(x)dx\\&=1-\Big(\int_0^{1-x_0}w(x)dx-\int_{1-x_0-\delta}^{1-x_0}w(x)dx\Big)\\&=1-\Big(\int_0^{1-x_0}w(x)dx-\delta w(1-x_0)\Big)\\&=w(x_0)+\delta w(1-x_0)\end{align*}$$
The above form is the first-principles definition of the derivative as $\delta\to 0$, and so we have $$w'(x)=w(1-x)$$Taking the derivative of both sides yields:
$$\begin{align*}w''(x)&=\frac{d}{dx}w(1-x)\\&=-w'(1-x)\\&=-w(x)\end{align*}$$
which is the harmonic oscillator differential equation with general solution $$w(x)=A\cos(x)+B\sin(x)$$for real constants $A,B$.
The boundary value we know is $w(1)=1$, which represents the fact that if the marker starts at $x=1$, then Robot 1 is guaranteed a win. We use this, in conjunction with the original differential equation. If we set $x=0$, on the right hand we have $$w(1-x)=w(1)=1$$while on the left we have
$$\begin{align*}w'(x)&=-A\sin(x)+B\cos(x)|_{x=0} \\&=-A\sin(0)+B\cos(0)\\&=B\end{align*}$$
and so $B=1$. Now, setting $x=1$, we have
$$\begin{align*}1&=w(1)\\&=A\cos(1)+\sin(1)\\\therefore A&=\frac{1-\sin(1)}{\cos(1)}\end{align*}$$
With the final equation $w(x)=\frac{1-\sin(1)}{\cos(1)}\cos(x)+\sin(x)$, we are ready to set $w(x)=\frac{1}{2}$, which returns $x=0.2149999$ correct to seven significant figures. However, we must return to our original labelling of the game interval. Hence, subtracting $0.5$ from the above number yields the initial marker position required for an even game: $$-0.2850001$$
A quick Python simulation of ten million games indeed confirms that the above starting position results in an even game.
Brief note
I really liked this puzzle because there were three really really unexpected things about it:
- The harmonic differential equation being involved was surprising. This is a problem about random variables and turn-taking, so it was very unexpected to see $w''(x)=-w(x)$ being integral to the solution.
- The use of 1 radian, specifically within $\cos(1)$ and $\sin(1)$. We almost never see integer radians being used, so this is quite remarkable. I don't intuitively see where this angle comes from. It's certainly unrelated to the game interval width (which has no impact on $w''(x)=-w(x)$) and also unrelated to the distribution of $a$ (so long as the upper limit is at least 1).
- The almost-neat decimal representation. Probably nothing in it, just a cool feature.