机器人公路旅行
Robot Road Trip
题目详情
机器人汽车具有最高速度（它们更愿意在驾驶时始终保持最高速度） 这是一个在每分钟 1 到 2 英里之间均匀随机抽取的实数。两车道 机器人汽车的高速公路有一条快车道（最低速度a）和一条慢车道（最低速度a） 最大速度a）。当同一车道上较快的汽车超过较慢的汽车时，较慢的汽车 车辆需要减速才能变道（如果两辆车都在快车道上起步） 或停在路肩上（如果两辆车都从慢车道出发）。机器人汽车减速并 以每分钟 1 英里的恒定速度加速，计时越快， 超车根本不需要变速，超车就发生了 瞬间。如果汽车很少见面（所以你永远不必更多地考虑汽车会议 比旅途中的另一辆车，请参阅下面的数学说明），并且您想要 最小化因超车而未行驶的里程，a 应该设置为多少，以英里为单位 分钟？请给出小数点后 10 位的答案。
汽车交互示例：假设a设置为每分钟 1.2 英里。如果一辆汽车有顶 速度 1.8 超过最高时速 1.1 的汽车，两者都不必减速，因为它们处于 不同的车道。如果最高时速为 1.8 的汽车超越了最高时速为 1.7 的汽车， 较慢的汽车计算开始减速 30 秒的最佳时间（以达到 以每分钟 1.2 英里的速度切换到另一条车道），因此速度更快的汽车会立即超车， 速度较慢的汽车可以立即开始加速，再加速 30 秒以恢复到 1.7 每分钟英里。此通行证花费 0.25 英里（较慢的汽车落后多远） 如果它继续以每分钟 1.7 英里的速度运行）。
如果一辆最高时速为 1.1 的汽车在慢车道上超越一辆最高时速为 1.0 的汽车，则较慢者 （最慢！）汽车必须减速整整一分钟直到 0 才能允许通过，并且 然后加速一分钟以恢复速度，正好损失 1 英里 距离。
假设所有汽车行程的长度恒定N，从任意点和时间开始 沿着无限长的高速公路。下面在数学上更加精确。
数学说明：假设汽车旅行以 z 个汽车旅行开始的速率到达 每英里每分钟，均匀地穿过无限的高速公路（汽车进出它们的 由于上/下坡道，以他们喜欢的速度行驶），并且汽车行程具有恒定的长度 N 英里。将 f(z,N) 定义为使预期损失最小化的 a 值 由于经过而每次汽车行驶的距离。查找：
[f(z,N) 的极限为 z -> 0+] 为 N -> 无穷大。
Robot cars have a top speed (which they prefer to maintain at all times while driving) that’s a real number randomly drawn uniformly between 1 and 2 miles per minute. A two-lane highway for robot cars has a fast lane (with minimum speed a) and a slow lane (with maximum speed a). When a faster car overtakes a slower car in the same lane, the slower car is required to decelerate to either change lanes (if both cars start in the fast lane) or stop on the shoulder (if both cars start in the slow lane). Robot cars decelerate and accelerate at a constant rate of 1 mile per minute per minute, timed so the faster, overtaking car doesn’t have to change speed at all, and passing happens instantaneously. If cars rarely meet (so you never have to consider a car meeting more than one other car on its trip, see Mathematical clarification below), and you want to minimize the miles not driven due to passing, what should a be set to, in miles per minute? Give your answer to 10 decimal places.
Example car interactions: suppose a is set to 1.2 miles per minute. If a car with top speed 1.8 overtakes a car with top speed 1.1, neither has to slow down because they are in different lanes. If instead the car with top speed 1.8 overtakes one with top speed 1.7, the slower car computes the optimal time to start decelerating for 30 seconds (to reach 1.2 miles per minute to switch to the other lane) so the faster car instantly passes and the slower car can immediately start accelerating for another 30 seconds to return to 1.7 miles per minute. This pass cost 0.25 miles (how far behind where the slower car would be if it continued at 1.7 miles per minute).
If a car with top speed 1.1 overtakes one with top speed 1.0 in the slow lane, the slower (slowest!) car must decelerate for a full minute all the way to 0 to allow the pass, and then accelerate for a full minute to reestablish its speed, losing exactly 1 mile of distance.
Assume all car trips are of constant length N, starting at arbitrary points and times along an infinitely long highway. This is made more mathematically precise below.
Mathematical clarification: Say car trips arrive at a rate of z car trip beginnings per mile per minute, uniformly across the infinite highway (cars enter and exit their trips at their preferred speed due to on/off ramps), and car trips have a constant length of N miles. Define f(z,N) to be the value of a that minimizes the expected lost distance per car trip due to passing. Find:
the limit of [the limit of f(z,N) as z -> 0+] as N -> infinity.
解析
Original Explanation
The trickiest part of this probability puzzle is determining the relative base rates between cars of different speeds overtaking each other. The notes about how cars rarely meet and all trips are the same long length N (made precise by taking limits) implies that we can minimize the “first order term” of the cost of exactly two cars meeting and we can ignore the boundary effects of meeting near the beginning or end of one of the cars’ journeys. We know each car’s speed is uniformly chosen in [1,2], so to find the relative rates of overtaking we can integrate over two speeds being drawn and then consider the set of positions in distance and time (which we are also given as being uniform) that the slower car would’ve had to start at to be overtaken by the faster car.
So say the two speeds we select are u < v, and without loss of generality we fix the position of the car traveling v to enter the highway at (0, 0) (the first coordinate is in distance and the second is in time). Then the car will exit the highway at (N, N/v), and the starting positions of the u-speed car that need to be overtaken by the v-speed car are those within the pictured parallelogram (again we are ignoring weirdness along the boundary because it will go to zero in the limit). A few different methods can compute the area of this parallelogram to be N2(1/u - 1/v). There are other ways to reason out this base rate but I like drawing parallelograms.
Now we must compute the cost of each overtake as a function of the speed of the overtaken car, it turns out to be in proportion to the square of the difference between u and the speed the car must reduce to. This implies we are trying to choose a to minimize the sum of the integrals pictured. The first integral is the cost of reducing speed from the slow lane to zero and the second integral is the cost of reducing speed from the fast lane to the slow lane. The N2 factors out and can be ignored, and some fundamental theorem of calculus and integration computing can get to an expression in a whose solution is 1.1771414168…
Congrats to all the solvers able to find the optimal speed limit!