Frictionless Tube

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:
$r_1 = 6\,563\,116$
$r_{j+1} = r_j^2 \bmod 32\,745\,673$
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)$.

We’ll also use the Python’s built-in function divmod which returns quotient and remainder:

“`
from collections import deque

def calc(L, N, j):
M = 32745673
current = 6563116
queue = deque()
queue.append(current % L)
direction = [1 if current <= 10**7 else -1] for _ in range(1, N): current = current * current % M pos = (current % 1000) + 1 if current <= 10**7: # Moving east pos += queue[-1] + 20 if pos > L: # Beyond the tube. Roll back to the valid range and change direction
pos, rem = divmod(pos – 20, L)
pos = L*pos + 20 + rem
direction[-1] = -1 # The last one now moving west
direction.append(1)
else: # Moving West
pos = queue[0] – pos – 20
if pos < 0: pos, rem = divmod(-pos - 20, L) pos = L*pos + 20 + rem direction[0] = 1 direction.insert(0, -1) queue.append(pos) cnt = [0]*len(queue) indx = 0 while len(queue) > 1:
if direction[indx] == 1: # Moving east
curr = queue.popleft()
indx, displ = divmod(queue[0] – curr, 20)
cnt[0] += displ + 20*indx
direction.pop(0)
direction[-1] = -1 # The last one now moving west
else: #Moving west
curr = queue.pop()
indx, displ = divmod(curr – queue[-1], 20)
cnt[-1] += displ + 20*indx
direction.pop()
direction[0] = 1
cnt.append(0)
return cnt[j-1]
print(calc(1000000000, 1000001, 500001))
“`
This program simulates the scenario as provided in the problem. But this might take forever to run because of the sheer scale of the scenario. Your best bet for solving this problem would be finding a way of optimizing the simulation or devising a clever way to solve the problem mathematically — which is non-trivial; hence this problem’s inclusion in Project Euler.

More Answers: