Solutions to past Jane Street puzzles that I've solved.
The puzzle statement for this month was:
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 -1. Each pull moves the marker a uniformly random draw from \( [0,1] \) towards the pulling robot. If the marker first leaves the interval \( [-1/2, 1/2] \) past \( 1/2 \), the first robot wins. If instead it first leaves the interval past \( -1/2 \), the second robot wins.
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!
Immediately after I saw this statement, I thought that there was likely an integral recurrence equation for the chance of winning the game from any particular position if a player gets to move first from that position. Indeed, this is so. The reason is that we can express the probability of player 1 winning the game if the marker is at a particular point as the integral over all of the possible outcomes of his move.
More precisely, let \( p: [-1/2, 1/2] \to [0, 1] \) be the chance of the first robot winning the game given that it gets to move at least once starting from some initial position. Trivially we have \( p(1/2) = 1 \), though we don’t necessarily have \( p(-1/2) = 0 \) because of the condition that the first robot is allowed to move at least once, which makes it more convenient to obtain an integral equation satisfied by \( p \). The chance of the first robot winning the game is the chance that after his move the second player will lose, in other words, we have
\[ p(x) = x + \frac{1}{2} + \int_x^{1/2} 1 - p(-t) \, dt = 1 - \int_x^{1/2} p(-t) \, dt \]
Differentiating on both sides now gives the differential equation \( p’(x) = p(-x) \), and differentiating on both sides again gives the familiar equation \( p’‘(x) = -p(x) \) whose general solution is \( c_1 \sin(x) + c_2 \cos(x) \). Therefore we only need to find the constants to determine \( p \), and we have two obvious constraints:
\[ p(1/2) = 1 \longrightarrow c_1 \sin(1/2) + c_2 \cos(1/2) = 1 \] \[ p’(x) = p(-x) \longrightarrow c_1 \cos(x) - c_2 \sin(x) = -c_1 \sin(x) + c_2 \cos(x) \]
Sine and cosine are linearly independent, so the second condition tells us that \( c_1 = c_2 = c \) for some \( c \), and the first condition then tells us that \( c = (\sin(1/2) + \cos(1/2))^{-1} \). Therefore we have the final answer
\[ p(x) = \frac{\sin(x) + \cos(x)}{\sin(1/2) + \cos(1/2)} \]
The question asks for the value \( x \) for which \( p(x) = 1/2 \). At this point I just used Wolfram Alpha to solve the equation, but if one had to compute it directly Newton’s method has quite fast convergence. Up to the desired precision we get the answer \( x \approx -0.2850001 \).