HMMT February, 2020

Combinatorics Difficulty 4.8 AIME Find the answer United States

Problem:
You have six blocks in a row, labeled $1$ through $6$ , each with weight $1$ . Call two blocks $x \leq y$ connected when, for all $x \leq z \leq y$ , block $z$ has not been removed. While there is still at least one block remaining, you choose a remaining block uniformly at random and remove it. The cost of this operation is the sum of the weights of the blocks that are connected to the block being removed, including itself. Compute the expected total cost of removing all the blocks.

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:
Note that the total cost is the total number of ordered pairs $(x, y)$ with $1 \leq x, y \leq 6$ such that $x$ and $y$ are connected right before $x$ gets removed.
The probability that blocks $x$ and $y$ are connected just before block $x$ is removed is simply $\frac{1}{|x-y|+1}$ , since all of the $|x-y|+1$ relevant blocks are equally likely to be removed first. Summing over $1 \leq x, y \leq 6$ , combining terms with the same value of $|x-y|$ , we get
$\frac{2}{6}+\frac{4}{5}+\frac{6}{4}+\frac{8}{3}+\frac{10}{2}+6=\frac{163}{10}$

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.