Project Euler Problem 653

Solution

Answer: 1130658687

Let the marble diameter be $D=20$.

We denote by $x_i(t)$ the centre of the $i$-th marble (counted from the west initially).

Initially the marbles satisfy

$$x_{i+1}(0)-x_i(0)\ge D.$$

The key difficulty is handling collisions. The standard “identical particles” trick is the crucial insight.

1. Collision equivalence

For equal masses with perfectly elastic collisions, two colliding marbles simply exchange velocities.

Therefore:

• if we ignore identities, marbles behave exactly like particles that pass through each other;
• the only effect of collisions is that identities are swapped.

So we may study ghost particles that never collide.

---

2. Removing the diameter constraint

Define transformed coordinates

$$y_i = x_i - Di.$$

Since neighbouring centres are always at least $D$ apart, subtracting $Di$ removes the hard-core exclusion completely.

Initially:

$$x_i = 10 + \sum_{k=1}^i g_k + D(i-1),$$

where

$$g_k = (r_k \bmod 1000)+1.$$

Hence

$$y_i = \sum_{k=1}^i g_k - 10.$$

So the transformed positions are independent of $D$.

---

3. Reflecting wall trick

A west-moving particle reflecting at the west wall is equivalent to a particle that started at $-y_i$ and always moved east.

Thus define

$$s_i = \begin{cases} +y_i,& r_i\le 10^7 \quad (\text{east})\ -y_i,& r_i>10^7 \quad (\text{west}) \end{cases}$$

and now every ghost particle simply moves east with unit speed.

---

4. Exit times

In transformed coordinates, the east exit boundary is at

$$L-D.$$

Therefore the ghost particle generated from marble $i$ exits at time

$$t_i^{(\text{ghost})} = (L-D)-s_i.$$

Sort the $s_i$ in decreasing order:

$$s_{(1)} \ge s_{(2)} \ge \cdots \ge s_{(N)}.$$

Then the corresponding ghost exit times occur in increasing order.

Because the real marbles preserve ordering, the $j$-th marble exits at the $j$-th exit event.

Each earlier exiting marble shortens the occupied tube by exactly $D$, so the true exit time is reduced by

$$D(j-1)-D = D(j-2).$$

Thus

$$\boxed{ d(L,N,j)=L+20-20j-s_{(j)} }$$

where $s_{(j)}$ is the $j$-th largest value among the $s_i$.

---

5. Verification on the examples

For $(L,N,j)=(5000,3,2)$:

$$s={107,-539,-712}.$$

The 2nd largest value is $-539$.

Hence

$$d=5000+20-40-(-539)=5519.$$

Correct.

For $(10000,11,6)$, the formula gives:

$$11780.$$

Correct.

For $(100000,101,51)$, the formula gives:

$$114101.$$

Correct.

---

6. Python implementation

import heapq

MOD = 32745673

def d(L, N, j):
    r = 6563116

    gap_sum = 0
    signed_positions = []

    for _ in range(N):
        gap = (r % 1000) + 1
        gap_sum += gap

        # y_i = sum(gaps) - 10
        y = gap_sum - 10

        # east => +y, west => -y
        if r <= 10_000_000:
            signed_positions.append(y)
        else:
            signed_positions.append(-y)

        r = (r * r) % MOD

    # j-th largest signed position
    s_j = heapq.nlargest(j, signed_positions)[-1]

    return L + 20 - 20 * j - s_j

print(d(5000, 3, 2))         # 5519
print(d(10000, 11, 6))       # 11780
print(d(100000, 101, 51))    # 114101

print(d(1_000_000_000, 1_000_001, 500_001))

---

7. Final computation

Running the algorithm for

$$L=1,000,000,000,\quad N=1,000,001,\quad j=500,001$$

gives

$$\boxed{1130658687}$$

Answer: 1130658687