HMMT February

Combinatorics Difficulty 5.8 AIME, harder Prove it United States

Problem:
The circumference of a circle is divided into $45$ arcs, each of length $1$ . Initially, there are $15$ snakes, each of length $1$ , occupying every third arc. Every second, each snake independently moves either one arc left or one arc right, each with probability $\frac{1}{2}$ . If two snakes ever touch, they merge to form a single snake occupying the arcs of both of the previous snakes, and the merged snake moves as one snake. Compute the expected number of seconds until there is only one snake left.

Solution

Solution:
We solve the problem generally for $n$ snakes and $3n$ arcs. Without loss of generality, fix the two snakes $A$ and $B$ that will eventually form the ends of the last snake. Note that $A$ and $B$ must be consecutive in the initial configuration; assume $B$ lies immediately clockwise from $A$ .

Let $d$ be the arclength between $A$ and $B$ (measuring clockwise from $A$ to $B$ ). As long as $d \neq 0$ and $d \neq 2n$ , we know that $A$ and $B$ lie in different snakes and thus move independently. Therefore, we can consider $d$ to be on a random walk starting at $2$ , where...

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.