Problem 653

Problem 653

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^2_j\mod 32\ 745\ 673$
The west-most marble is initially positioned with a gap of $(r_1 \mod 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\mod 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)$.




$r_1 = 6\ 563\ 116$
$r_{j+1}=r^2_j\mod 32\ 745\ 673$
最靠西的弹珠最初被摆在其表面上最西侧的点距离管道被封闭的西侧末端$(r_1 \mod 1000)+1$毫米的位置上。随后继续从西到东摆放弹珠,对于$2\le j\le N$,第$(j-1)$颗和第$j$颗弹珠表面之间最接近的两点距离恰好是$(r_j\mod 1000)+1$毫米。此外,如果$r_j\le 10\ 000\ 000$,则第$j$颗弹珠向东运动,反之如果$r_j>10\ 000\ 000$则向西运动。



记$d(L,N,j)$为第$j$颗弹珠在其球心从东侧开口末端离开管道前所运动的距离(以毫米计),因此$d(5000,3,2)=5519$。已知$d(10\ 000,11,6)=11\ 780$,$d(100\ 000,101,51)=114\ 101$。

求$d(1\ 000\ 000\ 000, 1\ 000\ 001, 500\ 001)$。