Train Tracks with Gaps: Applying the Probabilistic Method to Trains
  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
$\Theta( \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.
