Rainbow Train Rearrangement
A train has three cars: Red, Green, and Blue. The conductor can perform one operation as many times as they like: disconnect all cars behind the front car and move them to the front, cycling the rear car to the leading position.
More precisely, at each step the conductor takes the rearmost car and places it at the front of the train. The cars start in a uniformly random order.
What is the probability that the conductor can rearrange the train into rainbow order (Red, then Green, then Blue)?
Hints
- Think concretely about what the conductor's operation does to the sequence of cars -- what mathematical operation is it?
- The conductor can perform the operation any number of times. What is the maximum number of distinct arrangements reachable from a single starting point?
- List all 6 possible orderings and check which ones can be transformed into $(1,2,3)$ by repeated rear-to-front rotation. You should find exactly half of them can.
Worked Solution
How to Think About It: First name the operation: taking the rear car to the front is a cyclic rotation of the three cars. So the conductor's *entire* toolkit is rotate-0, rotate-1, rotate-2 times — after three rotations you're back to start. The heuristic is orbit counting: the reachable arrangements from any start form one rotation orbit of size $3$, and the target is reachable iff the start lies in the target's orbit. The naive trap is to assume any of the $3!=6$ orders can be reached — but rotation cannot change the *cyclic order* of the colors, only where you cut the cycle.
Quick Estimate: No heavy math needed — count the orbit in your head. Rotation preserves cyclic order, and the $6$ permutations of three distinct items split into exactly two cyclic classes: the clockwise cycle $R\to G\to B$ and its mirror $R\to B\to G$. Rainbow order sits in one class of size $3$; a uniformly random start lands in that class with probability $\tfrac{3}{6}=\tfrac12$. That's the answer.
Approach: Count starting permutations in the target's rotation orbit, divide by $3!$.
Formal Solution: Label rainbow order $R=(1,2,3)$ (Red, Green, Blue). Applying the rotation (rear to front) repeatedly: $$(1,2,3)\;\xrightarrow{\text{rot}}\;(3,1,2)\;\xrightarrow{\text{rot}}\;(2,3,1)\;\xrightarrow{\text{rot}}\;(1,2,3).$$ So the target's orbit is $$\text{Orbit}_1 = \{(1,2,3),\,(3,1,2),\,(2,3,1)\}.$$ The other three permutations form a disjoint orbit that never reaches the target: $$\text{Orbit}_2 = \{(1,3,2),\,(2,1,3),\,(3,2,1)\},\qquad (1,3,2)\to(2,1,3)\to(3,2,1)\to(1,3,2).$$ Each orbit has size $3$ because $\mathbb{Z}_3$ acts freely on the $3$ distinct cars. The conductor reaches rainbow order iff the start is in $\text{Orbit}_1$. With a uniform start: $$P = \frac{|\text{Orbit}_1|}{3!} = \frac{3}{6} = \boxed{\tfrac12}.$$
Answer: $\dfrac{1}{2}$.
Intuition
The conductor's operation is a cyclic rotation -- it generates a group of exactly 3 distinct permutations (for 3 cars). Because the group has size 3 and the total number of permutations is 6, the 6 arrangements split into exactly two equal orbits of size 3. You either start in the right orbit or you do not, and there is nothing the conductor can do to escape the orbit they start in. So the answer is exactly 1/2, with no approximation needed.
This is a clean illustration of how group theory structures counting problems. In general, if a group $G$ of size $|G|$ acts on a set $S$ of size $|S|$, the orbits partition $S$ into equal pieces (when the action is free), and the fraction reachable from any target is $|G|/|S|$. For 3 cars, $|G| = 3$ and $|S| = 6$, giving $1/2$. The same logic applies in more complex settings -- for example, figuring out which configurations of a Rubik's cube are reachable from the solved state, or understanding why certain sorting networks can only produce even permutations.