Library / /61 of 84

, 2013

Combinatorics Difficulty 5.6 AIME, harder Prove it United States

Problem:

For an even positive integer $n$ , Kevin has a tape of length $4n$ with marks at $-2n, -2n+1, \ldots, 2n-1, 2n$ . He then randomly picks $n$ points in the set $-n, -n+1, -n+2, \ldots, n-1, n$ , and places a stone on each of these points. We call a stone 'stuck' if it is on $2n$ or $-2n$ , or either all the points to the right, or all the points to the left, all contain stones. Then, every minute, Kevin shifts the unstuck stones in the following manner:

- He picks an unstuck stone uniformly at random and then flips a fair coin.
- If the coin came up heads, he then moves that stone and every stone in the largest contiguous set containing that stone one point to the left. If the coin came up tails, he moves every stone in that set one point right instead.
- He repeats until all the stones are stuck.

Let $p_{k}$ be the probability that at the end of the process there are exactly $k$ stones in the right half. Evaluate
$\frac{p_{n-1}-p_{n-2}+p_{n-3}-\ldots+p_{3}-p_{2}+p_{1}}{p_{n-1}+p_{n-2}+p_{n-3}+\ldots+p_{3}+p_{2}+p_{1}}$
in terms of $n$ .

Solution

Solution:

Answer: $\frac{1}{n-1}$

After we have selected the positions of the initial $n$ stones, we number their positions: $a_{1} < a_{2} < \ldots < a_{n}$ . The conditions on how we move the stones imply that the expected value of $\left(a_{i}-a_{j}\right)$ after $t$ minutes is still equal to $a_{i}-a_{j}$ . In addition, if $b_{i}$ is the final position of the $i$ th stone, $E\left(b_{i+1}-b_{i}\right) = E\left(a_{i+1}-a_{i}\right)$ . But this quantity is also equal to $(3n+2) \cdot p_{i} + 1 \cdot (1-p_{i})$ .

Now, let's calculate the expected value of $a_{i+1}-a_{i}$ . This is the sum over $g = a_{i+1} - a_{i}$ , and $j$ , the number of spaces before $a_{i}$ of $g \cdot \binom{j}{i-1} \binom{2n-j-g}{n-i+1}$ , so we get
$\frac{1}{\binom{2n+1}{n}} \sum_{g} g \cdot \sum_{j} \binom{j}{i-1} \binom{2n-j-g}{n-i-1}$
But $\sum_{j} \binom{j}{i-1} \binom{2n-j-g}{n-i-1}$ is just $\binom{2n-g+1}{n-1}$ . Therefore the expected value of $a_{i+1}-a_{i}$ is independent of $i$ , so $p_{i}$ is constant for all $i \neq 0, n$ . It follows that the answer is $\frac{1}{n-1}$ .

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

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