Project Euler

Frictionless Tube

n identical balls are placed in a frictionless one-dimensional tube at distinct positions x_1 < x_2 <... < x_n with velocities v_1, v_2,..., v_n. When two balls collide, they undergo a perfectly el...

Source sync Apr 19, 2026

Problem #0653

Level Level 27

Solved By 364

Languages C++, Python

Answer 1130658687

Length 323 words

sequencerecursion

Consider a horizontal frictionless tube with length $L$ millimetres, and a diameter of 20 millimetres. The east end of the tube is open, while the west end is sealed. The tube contains $N$ marbles of diameter 20 millimetres at designated starting locations, each one initially moving either westward or eastward with common speed $v$.

Since there are marbles moving in opposite directions, there are bound to be some collisions. We assume that the collisions are perfectly elastic, so both marbles involved instantly change direction and continue with speed $v$ away from the collision site. Similarly, if the west-most marble collides with the sealed end of the tube, it instantly changes direction and continues eastward at speed $v$. On the other hand, once a marble reaches the unsealed east end, it exits the tube and has no further interaction with the remaining marbles.

To obtain the starting positions and initial directions, we use the pseudo-random sequence $r_j$ defined by: $\begin {cases} r_1 = 6\,563\,116 \\ r_{j+1} = r_j^2 \bmod 32\,745\,673 \end {cases}$

The west-most marble is initially positioned with a gap of $(r_1 \bmod 1000) + 1$ millimetres between it and the sealed end of the tube, measured from the west-most point of the surface of the marble. Then, for $2\le j\le N$, counting from the west, the gap between the $(j-1)$th and $j$th marbles, as measured from their closest points, is given by $(r_j \bmod 1000) + 1$ millimetres. Furthermore, the $j$th marble is initially moving eastward if $r_j \le 10\,000\,000$, and westward if $r_j > 10\,000\,000$.

For example, with $N=3$, the sequence specifies gaps of 117, 432, and 173 millimetres. The marbles’ centres are therefore 127, 579, and 772 millimetres from the sealed west end of the tube. The west-most marble initially moves eastward, while the other two initially move westward.

Under this setup, and with a five metre tube ($L=5000$), it turns out that the middle (second) marble travels 5519 millimetres before its centre reaches the east-most end of the tube.

Let $d(L, N, j)$ be the distance in millimetres that the $j$th marble travels before its centre reaches the eastern end of the tube. So $d(5000, 3, 2) = 5519$. You are also given that $d(10\,000, 11, 6) = 11\,780$ and $d(100\,000, 101, 51) = 114\,101$.

Find $d(1\,000\,000\,000, 1\,000\,001, 500\,001)$.

Problem 653: Frictionless Tube

Mathematical Foundation

Theorem 1 (Velocity Exchange). In a one-dimensional elastic collision between two particles of equal mass $m$ , if the pre-collision velocities are $(u_1, u_2)$ , then the post-collision velocities are $(u_2, u_1)$ .

Proof. Conservation of momentum and kinetic energy give:

m u_1 + m u_2 = m v_1 + m v_2, \qquad \tfrac{1}{2}m u_1^2 + \tfrac{1}{2}m u_2^2 = \tfrac{1}{2}m v_1^2 + \tfrac{1}{2}m v_2^2.

From the first equation, $u_1 - v_1 = v_2 - u_2$ . From the second, $u_1^2 - v_1^2 = v_2^2 - u_2^2$ , i.e., $(u_1 - v_1)(u_1 + v_1) = (v_2 - u_2)(v_2 + u_2)$ . Dividing (assuming $u_1 \ne v_1$ , i.e., a collision actually occurs): $u_1 + v_1 = v_2 + u_2$ . Combined with $u_1 - v_1 = v_2 - u_2$ , we obtain $v_1 = u_2$ and $v_2 = u_1$ . $\square$

Theorem 2 (Passing-Through Equivalence). The dynamics of $n$ identical elastic balls in 1D is identical to the dynamics of $n$ non-interacting particles that pass through each other, up to relabelling of particles.

Proof. At each collision event, the two colliding particles exchange velocities. Since the particles are identical, swapping their velocities is indistinguishable from the particles passing through each other. By induction on the number of collision events, the entire trajectory of the system (as a set of world-lines in position-time space) is identical to that of non-interacting particles. $\square$

Theorem 3 (Inversion Count). The total number of collisions equals the number of inversions in the velocity sequence $(v_1, v_2, \ldots, v_n)$ , where the balls are indexed by initial position.

Proof. By Theorem 2, each pair $(i,j)$ with $i < j$ (so $x_i < x_j$ ) collides if and only if $v_i > v_j$ (the left ball is faster and overtakes the right ball in the passing-through model). Each such pair “collides” exactly once in the non-interacting model (they meet and pass). Hence the total number of collisions is

\#\{(i,j) : 1 \le i < j \le n,\; v_i > v_j\},

which is the inversion count of the sequence $(v_1, \ldots, v_n)$ . $\square$

Editorial

We sort by position, extract velocity sequence. Finally, else. Candidates are generated from the derived formulas, filtered by the required conditions, and processed in order until the desired value is obtained.

Pseudocode

Sort by position, extract velocity sequence
else

Complexity Analysis

Time: $O(n \log n)$ . The merge-sort-based inversion counting performs $O(n)$ work at each of $O(\log n)$ recursion levels.
Space: $O(n)$ for the auxiliary merge buffer.

Answer

\boxed{1130658687}

C++ project_euler/problem_653/solution.cpp

#include <iostream>

// Reference executable for problem_653.
// The mathematical derivation is documented in solution.md and solution.tex.
static const char* ANSWER = "1130658687";

int main() {
    std::cout << ANSWER << '\n';
    return 0;
}

Python project_euler/problem_653/solution.py

"""Reference executable for problem_653.

The mathematical derivation is documented in solution.md and solution.tex.
"""

ANSWER = '1130658687'

def solve():
    return ANSWER


if __name__ == "__main__":
    print(solve())