1..9 绕圆排列：最小化相邻差绝对值和的概率

九点分布圆

专题: Probability / 概率
难度: L4
来源: QuantQuestion

题目详情

If $x_{1},x_{2},\ldots ,x_{9}$ is a random arrangement of numbers $1,2,\ldots ,9$ around a circle, what is the probability that $\textstyle \sum_{i = 1}^{9}\left|x_{i + 1} - x_{i}\right|$ is minimized? (Here, $x_{10} = x_{1}$ .)

解析

记

S=\sum_{i=1}^9 |x_{i+1}-x_i|,\quad x_{10}=x_1.

不妨固定旋转使 $x_1=1$ 。

令 $x_k=9$ 。由三角不等式可得 $S\ge |9-1|+|1-9|=18$ ，且当且仅当从 1 到 9 的那一段严格递增、从 9 回到 1 的那一段严格递减时取到 18。

对给定 $k$ ，只需从 $\{2,3,\ldots,8\}$ 中选 $k-2$ 个放在 1 与 9 之间并按递增排列，其余按递减放在 9 与 1 之间，因此最小配置数为

\sum_{k=2}^{9}\binom{7}{k-2}=2^7=128.

总排列数在 $x_1=1$ 下为 $8!$ ，所以所求概率为

\boxed{\frac{128}{8!}=\frac{1}{315}}.