论文标题
带有空白的火车轨道：将概率方法应用于火车
Train Tracks with Gaps: Applying the Probabilistic Method to Trains
论文作者
论文摘要
我们确定了火车车上车轮数量之间的权衡曲线，以及必须安装的轨道数量，以确保火车车始终由轨道支撑。目的是建立一个覆盖较大距离$ \ ell $的高架轨道，但主要由差距组成，以便实际安装的火车轨道总数仅为$ \ ell $的一小部分。为了使火车轨道可以在所有点上支撑火车，因此要求是，随着火车越过轨道，从后季度到至少一组车轮，而火车前季度的至少一组车轮必须始终触及轨道。 我们表明，如果火车车在其后部有$ n $ n $的车轮均匀间隔，并且$ n $ n $的车轮在其前面均匀间距均匀，那么可以构建一个支持火车车的火车轨道，但只使用$θ（\ ell / n）$英尺的轨道。然后，我们考虑如果火车车上的车轮不均匀间距会发生什么（甚至可以对抗）。我们表明，对于火车车的任何配置，汽车的每个前区和后四分之一都有$ n $ wheels，可以构建一条轨道，该轨道为距离$ \ ell $ $ \ ell $且仅使用$ o \ left（\ frac {\ ell \ ell \ log n} {n} {n} {n} {n} \ right）$ firt track $ figt。此外，我们表明，该折衷曲线在渐近上是最佳的火车车配置。上限和下限都是通过概率方法的应用实现的。
We identify a tradeoff curve between the number of wheels on a train car, and the amount of track that must be installed in order to ensure that the train car is supported by the track at all times. The goal is to build an elevated track that covers some large distance $\ell$, but that consists primarily of gaps, so that the total amount of feet of train track that is actually installed is only a small fraction of $\ell$. In order so that the train track can support the train at all points, the requirement is that as the train drives across the track, at least one set of wheels from the rear quarter and at least one set of wheels from the front quarter of the train must be touching the track at all times. We show that, if a train car has $n$ sets of wheels evenly spaced apart in its rear and $n$ sets of wheels evenly spaced apart in its front, then it is possible to build a train track that supports the train car but uses only $Θ( \ell / n )$ feet of track. We then consider what happens if the wheels on the train car are not evenly spaced (and may even be configured adversarially). We show that for any configuration of the train car, with $n$ wheels in each of the front and rear quarters of the car, it is possible to build a track that supports the car for distance $\ell$ and uses only $O\left(\frac{\ell \log n}{n}\right)$ feet of track. Additionally, we show that there exist configurations of the train car for which this tradeoff curve is asymptotically optimal. Both the upper and lower bounds are achieved via applications of the probabilistic method.
