July 2025: Robot Road Trip

What a contrast it was to follow one of my favourite Jane Street puzzles of all time in June with one of my least favourites in July! For the most part, my complaint is that the puzzle felt uncharacteristically inelegant for Jane Street, but there were several factors contributing to this. For one thing, this is a very mathematically messy problem. The mess can be largely avoided by making some fairly natural simplifications, but their justification is actually of a fairly technical nature, meaning that almost everyone who solved the problem (myself included) will probably have done so by largely ignoring some complicating factors which just so happen to have no bearing on the answer. For another thing, the wording is careless; for example, we’re told to assume the car trips are of “constant” length \(N\), but then we’re told in the mathematical clarification that we’re actually taking the limit as \(N\) approaches infinity… so the car trips aren’t of constant length at all? Finally, the quantity we’re tasked with computing simply doesn’t seem very interesting. For any fixed \(N\), the probability of a given car meeting any other car approaches \(0\) in the limit as \(z\) approaches \(0\), hence the expected lost distance per car trip (as a function of \(a\)) limits uniformly to \(0\). That is, any value of \(a\) will eventually be just as good as any other, and we’re effectively optimising an event that will almost surely never happen anyway.

Given my frustration with the problem, it may not come as too much of a surprise that it was actually me (or at least partially me) who led to the mathematical clarification being posted. Prior to this, it was unclear how to process and interpret all the information, especially the car trips being of “constant” length \(N\), and what underlying process governed the “spawn points” of the cars in spacetime. As such, in my first attempt, I didn’t have much choice but to make the naive assumption that every car will meet another car exactly once, and I submitted an incorrect answer based on this, together with a comment on what I thought was unclear and why. I’ve seen Jane Street puzzles edited after their initial postings a handful of times, but this was the first time I’ve contributed to that, so that at least provided some extra excitement for me surrounding this month’s puzzle.

Stats:

Difficulty: 7/10

Enjoyability: 3/10

Leaderboard Placing: 7/242

The approach:

The first order of business is to work out how much distance is lost when a car decelerates from some speed \(v_1\) down to \(v_2\) and then accelerates from \(v_2\) back up to \(v_1\). With the help of some basic calculus — or the types of tools one uses in early high school physics — it can be seen that a distance of \((v_1 - v_2)^2\) is lost in this process.

Now, fix \(N, z > 0\) and \(a \in [1,2]\), and consider a single car “spawning” at some point in spacetime, which we will visualise as the \((x,t)\)-plane. We wish to compute the expected distance lost during this car’s trajectory due to interactions with other cars. Denoting this lost distance by \(L\), it follows by the law of total expectation, since the velocity \(U\) of the car under consideration is uniformly distributed in \([1,2]\), that we have

Regardless of the velocity \(u \in [1,2]\), the given car may interact with either zero cars or one other car on its trajectory (noting that we’re told not to consider the possibility of a car meeting any more than one other car). If the given car interacts with no other cars, we clearly have \(L = 0\), and such cases contribute nothing to the expectation. We further decompose the case of exactly one interaction according to the velocity \(V\) of the other car involved. Denoting by \(M(u,v)\) the event that a given car with velocity \(u\) will meet another car with velocity \(v\), we again have by the law of total expectation that

The probability of the event \(M(u,v)\) is easy enough to compute: for the sake of visualisation, assume without loss of generality that the original car under consideration (the one with velocity \(u\)) spawned at the origin; then, its trajectory through spacetime is given by the line segment \(\{(us, s) : s \in [0, N/u]\}\). Similarly, the trajectory of any car with velocity \(v\) forms a line segment of the form \(\{(x_0 + vs, t_0 + s) : s \in [0, N/v]\}\). The two cars of velocities \(u\) and \(v\) will meet if and only if the two line segments intersect, and it’s geometrically clear that this is the case if and only if the car with velocity \(v\) spawns within a certain parallelogram in the \((x,t)\)-plane. One pair of sides of this parallelogram are translates of the the vector \((N, N/u)\), and the other pair of sides are translates of the vector \((N, N/v)\). Computing a simple determinant reveals that the parallelogram has area \(A_N(u,v) := N^2\left|\frac{1}{u}-\frac{1}{v}\right|,\) and since cars spawn at a rate of \(z\) per mile per minute (implicitly according to a Poisson process in the \((x,t)\)-plane), we conclude that \(\mathbb{P}(M(u,v)) = zA_N(u,v)e^{-zA_N(u,v)}\).

Recalling that \(a \in [1, 2]\) was fixed, we may now decompose the double integral expression we have for \(\mathbb{E}[L]\) as follows:

(where we omit the integrand to save space; note that there are also terms of the form \(\int_1^a\int_a^2\,dv\,du\) and \(\int_a^2\int_1^a\,dv\,du\), but these vanish since no cars have to slow down in these cases, hence no distance is lost). We denote the above integrals by \(I_1\), \(I_2\), \(I_3\), \(I_4\) respectively, and we denote the integrand by \(I_{N,z}(u,v) := zA_N(u,v)e^{-zA_N(u,v)}\mathbb{E}[L | U=u,\, M(u,v)]\). It’s the \(\mathbb{E}[L | U=u,\, M(u,v)]\) term which is problematic, and it’s here that we’ll cut some corners in a way that seems to have been intended by the author of the puzzle.

We already know how much distance will is lost in the case that a car has to decelerate to a given velocity and then accelerate back to its initial velocity. The main technicality, however, is that there will be cases in which two cars meet and one has to slow down to accommodate the other, but will finish its journey by the time it fully returns to its original speed; the distance lost in such cases is complicated and difficult to account for exactly. I believe the region of spacetime in which the second car must spawn in order for this to become relevant is a sub-parallelogram of the original parallelogram with area \(O(N)\), which will contribute negligibly to the expectation in the limit as \(N\) approaches infinity, but again, I believe such subtleties were intended to be ignored, so let’s assume that any interaction between two cars allows for a full deceleration and re-acceleration. We then have four cases:

• In the case of \(I_1\), we have \(1 < v < u < a\), hence \(\mathbb{E}[L | U=u,\, M(u,v)] = v^2\).
• In the case of \(I_2\), we have \(1 < u < v < a\), hence \(\mathbb{E}[L | U=u,\, M(u,v)] = u^2\).
• In the case of \(I_3\), we have \(a < v < u < 2\), hence \(\mathbb{E}[L | U=u,\, M(u,v)] = (v-a)^2\).
• In the case of \(I_4\), we have \(a < u < v < a\), hence \(\mathbb{E}[L | U=u,\, M(u,v)] = (u-a)^2\).

We see from the above cases that the expression \(\mathbb{E}[L | U=u,\, M(u,v)]\) is symmetric in \(u\) and \(v\). Since this is also true of the term \(zA_N(u,v)e^{-zA_N(u,v)}\), we conclude that the entire integrand \(I_{N,z}(u,v)\) is symmetric, and we have by a simple application of Fubini’s theorem that

The above expression has some minimum in \(a\), and we wish to find the limit of the location of this minimum as \(z\) approaches \(0\). Since all quantities involved are smooth, it’s not hard to see that this may be found by first dividing out by \(2z\) (which doesn’t affect the location of the minimum), then taking the limit as \(z\) approaches \(0\) (via the dominated convergence theorem), and finally locating the minimum of the resulting function of \(a\). The result of diving out by \(2z\) and taking limits is as follows, as seen in the explanation posted by Jane Street:

To locate the minimum in \(a\), we divide out by \(N^2\) and differentiate by repeated applications of the Leibniz integral rule, finding

Though cumbersome, this expression may be computed without difficulty and expressed in terms of familiar analytic functions. Applying a root-finding function from any number of Python libraries then reveals the answer of 1.1771414168, to the desired level of accuracy. We note that according to the mathematical clarification, we must technically take the limit as \(N\) approaches infinity, but there’s no longer a dependence on \(N\) anyway.