A Train Problem

Published Jul 5, 2022

First blog post, mostly messing around with formatting here. This is powered by MDsveX with custom layouts, with plugin support for syntax highlighting and $\LaTeX$.

On an infinitely long track, $n$ train cars, each with a half chance of containing dynamite, start evenly spaced and all head towards the same direction at distinct constant speeds. When a train $A$ catches up to another train $B$, the front of $A$ connects to the back of $B$ to become a longer train. The new train continues moving at the same speed as $B$. After a long time has passed (such that no new train connections will take place), the trains halt and are inspected. A train is safe if it has two consecutive train cars not carrying dynamite, otherwise it is dangerous. All dangerous trains are removed from the track due to safety hazards, and the total amount of removed train cars is $N$. As $n$ tends to infinity, $\mathbb{E}(N)$ converges to some value. Find this value.

— Modified PROMYS 2022 Q10

Solution

The key idea is to consider the slowest train $T$. Note that:

• All trains behind $T$ will at some point all merge into $T$.
• All trains ahead of $T$ will never interact with $T$ or the trains behind it. So, they form their own system with the same conditions in the problem statement.

We can apply a recursion. Define $f(x)$ to be the probability that a train of length $x$ (consisting of $x$ train cars) is dangerous. Note $xf(x)$ is the expected value of train cars removed from this train; it’s 0 if it’s not dangerous but $x$ if it is.

We have

Here we iterate over all $i$, the possible positions of the slowest train, and sum the expected value $i f(i) + \mathbb{E}(n - i)$ (a train of length $i$ and a new system with $n - i$ train cars) in each case, and finally take the average.

We simply the recursion by considering $\mathbb{E}(n + 1) - \mathbb{E}(n)$:

Remove the weights,

$f(0) = 0$, hence

Lemma

$f(n) = \frac{F_{n + 2}}{2^n}$, where $F_i$ is the $i$-th Fibonnaci number.

Note $f(n) = \frac{g(n)}{2^n}$, where $g(n)$ is the number of possible length $n$ dangerous trains. Consider the first train car. If it contains dynamite, the entire train is dangerous if and only if the rest (without the first train car) of the train is dangerous. If it doesn’t contain dynamite, the next train car must contain dynamite, and then the rest of the train must be dangerous. $g(n) = g(n - 1) + g(n - 2)$, and $g(1) = 2$, $g(2) = 3$. Thus $g(n) = F_{n + 2}$. $\blacksquare$

It remains to determine

Note convergence. Now standard techniques will finish.

Solving yields

Then

Something Else

Here’s a distance estimator for the Sierpenski Pyramid from Syntopia.

// In GLSL, theme is Github Dark 
float pyramidDE(float scale, float offset, int iterations, vec3 p){
    for (int n = 0; n < iterations; ++n) {
        if (p.x + p.y < 0.0){ 
            p.xy = - p.yx;
        } 
        if (p.x + p.z < 0.0){ 
            p.xz = - p.zx;
        } 
        if (p.y + p.z < 0.0){ 
            p.zy = - p.yz;
        } 
        p = p * scale - offset * (scale - 1.0);
    }

    return length(p) * pow(scale, float(-iterations));
}