HMMT 二月 2020 · 冲刺赛 · 第 15 题
HMMT February 2020 — Guts Round — Problem 15
题目详情
英文原题
- [8] You have six blocks in a row, labeled 1 through 6, each with weight 1. Call two blocks x ≤ y connectedwhen, for all x ≤ z ≤ 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 sumof the weights of the blocks that are connected to the block being removed, including itself. Compute theexpected total cost of removing all the blocks.
解析
英文解析
- [8] You have six blocks in a row, labeled 1 through 6, each with weight 1. Call two blocks x ≤ yconnected when, for all x ≤ z ≤ y, block z has not been removed. While there is still at least one blockremaining, you choose a remaining block uniformly at random and remove it. The cost of this operationis 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.
Proposed by: Benjamin Qi
Answer:163
Solution: Note that the total cost is the total number of ordered pairs ( x, y ) with 1 ≤ x, y ≤ 6 such 10
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 , since 1
| x − y | +1
all of the | x − y | + 1 relevant blocks are equally likely to be removed first. Summing over 1 ≤ x, y ≤ 6 ,
combining terms with the same value of | x − y | , we get
2 4 6 8 10 163 + + + + + 6 = .
6 5 4 3 2 10