IOQM 2024 Q14 particle movement

Q14(combinatorics). Initially, there are \(3^{80}\) particles at the origin (0,0). At each step the particles are moved to points above the x-axis as follows: if there are n particles at any point (x,y), then \(\left\lfloor \frac{n}{3} \right\rfloor\) of them are moved to (x+1, y+1), \(\left\lfloor \frac{n}{3} \right\rfloor\) are moved to (x, y+1) and the remaining to (x-1, y+1).

For example, after the first step, there are \(3^{79}\) particles each at (1,1), (0,1) and (-1,1). After the second step, there are \(3^{78}\) particles each at (-2,2) and (2,2), \(2 \times 3^{78}\) particles each at (-1,2) and (1,2), and \(3^{79}\) particles at (0,2). After 80 steps, the number of particles at (79,80) is:

Solution:

Original problem has large numbers like 3^80. So let's see how to solve a smaller problem.
Let there be 3^2 particles with the same rules.
Let's figure out what happens after 2 steps.

Initially 9 particles at (0,0)
First step:
(0,1): 3 particles
(1,1): 3 particles
(-1,1): 3 particles

Second step:
From (0,1):
1 on (0,2).
1 on (1,2).
1 on (-1,2).

From (1,1):
1 on (0,2).
1 on (1,2).
1 on (2,2).

From (-1,1):
1 on (0,2).
1 on (-1,2).
1 on (-2,2).

In the first step we had 3 subgroups and each of them  size 3.
In the second step we had 9 subgroups and each of them size 1.
Now, list the positions with number of particles:
3 on (0,2)
2 on (1,2)
2 on (-1,2)
1 on (2,2)
1 on (-2,2)

Let's figure out the possible paths taken by particles to reach on each co-ordinate:
(0,0) to (0,2) => RL,LR,SS => 3 particles = 2!/(1!.1!) + 2!/2!
(0,0) to (1,2) => RS,SR => 2 particles = 2!/(1!.1!)
(0,0) to (-1,2) => LS,SL => 2 particles = 2!/(1!.1!)
(0,0) to (2,2) => RR => 2 particles = 2!/2!
(0,0) to (-2,2) => LL => 1 particles = 2!/2!

So number of particles at a co-ordinate is same as number of ways to reach there.
And each particle took a different path to reach its destination.
Extending the same logic to 3^80 particles:

Problem restatement

• We start with $3^{80}$ particles at $(0,0)$.

• During each of 80 “time steps” every particle moves exactly one unit up ( $y\gets y+1$ ) and, horizontally, chooses

  • R : $(x,y)\to(x+1,y+1)$

  • S : $(x,y)\to(x ,y+1)$

  • L : $(x,y)\to(x-1,y+1)$

Because $3^k$ is divisible by 3 for every $k>0$, the rule “$\bigl\lfloor n/3\bigr\rfloor,\bigl\lfloor n/3\bigr\rfloor,\text{remainder}$” always splits each clump perfectly evenly. Consequently:

• After 1 split every subgroup has size $3^{79}$;

• after 2 splits every subgroup has size $3^{78}$;

• …

• after 80 splits every subgroup has size $3^{80-80}=3^{0}=1$.

Hence each of the $3^{80}$ particles follows a distinct 80‑step word of $R,S,L$; there is a one‑to‑one correspondence

$$\boxed{\text{particles} \;\longleftrightarrow\; \text{all }3^{80}\text{ possible sequences of }R,S,L\text{ of length }80}.$$

---

Coordinates after 80 steps

Let a particular particle use

• $r$ right moves ($R$),

• $l$ left moves ($L$),

• $s$ straight moves ($S$),

with $r+l+s = 80$.

The net horizontal displacement is

$$x = (+1)\,r + (0)\,s + (-1)\,l = r - l .$$

We want the particles that finish at $(79,80)$.
Thus

$$\begin{cases} r-l = 79,\\[4pt] r+l+s = 80. \end{cases}$$

Solve the system

1. $l = r - 79$ (from the first equation);

2. Substitute in the second: $r + (r-79) + s = 80 \;\Longrightarrow\; 2r + s = 159$.

Because $r,l,s$ are non‑negative integers:

• $l\ge 0 \;\Rightarrow\; r \ge 79$,

• $s\ge 0 \;\Rightarrow\; 2r \le 159\;\Rightarrow\; r \le 79.5$.

The only integer satisfying both is $r = 79$.
Then $l = 0$ and $s = 159-2\cdot79 = 1$.

So every particle that ends at $(79,80)$ must have

$$\underbrace{79}_{r}\text{ rights},\quad \underbrace{1 }_{s}\text{ straight},\quad \underbrace{0 }_{l}\text{ left}.$$

---

Counting the admissible paths

Place the single $S$ somewhere among the 80 steps; the remaining 79 steps are all $R$.
The number of distinct orderings is the multinomial count

$$\frac{80!}{79!\,1!\,0!} \;=\; 80.$$

Because each path corresponds to exactly one particle at time 80, we obtain

$$\boxed{\text{particles at }(79,80)\;=\;80 }.$$

---

Quick sanity check with the statement’s example

After two steps the problem statement reports

• $3^{78}$ particles at $(-2,2)$ and $(2,2)$ (paths $RL$ and $LR$),

• $2\!\cdot\!3^{78}$ at $(-1,2)$ and $(1,2)$ (two paths each),

• $3^{79}$ at $(0,2)$ (three paths).

Indeed these multiplicities match the number of admissible 2‑step sequences that reach each $x$.

The identical reasoning extended to 80 steps gives a total of 80 admissible sequences reaching $x=79$, confirming the result.

________________

Now, what if I modify the problem like this:
Initially there are 2^80 particles and at each step half the particles move to (x,y+1) and other half to (x+1,y+1). Then how many will be there at (79,80) after 80 steps?
Answer: 80 again.

Coming back to original problem, how many will there be at (78,80) and (77,80) after 80 moves?
A. For (78,80) there are 2 ways:
A1. 78R + 2S = 80!/(78!.2!)
A2. 79R + 1L = 80!(79!)
Add them to get the answer.

B. For (77,80):
B1. 77R, 3S = 80!/(77!3!)
B2. 78R, 1L, 1S = 80!/(78!)
Add them to get the answer.
____________________________