返回题库

圆周折线穿越计数

Segment Traversal

专题
Probability / 概率
难度
L6

题目详情

在圆周上随机取点:先取 P1P_1,再取 P2P_2 并连线 P1P2P_1P_2;继续取 P3,,PnP_3,\dots,P_n,每次连接 PiPi+1P_iP_{i+1};最后连 PnP1P_nP_1

问:圆内部线段交点数的期望作为 nn 的函数是什么?并计算 n=12n=12 时的值。

You select a uniformly random starting point on the circumference of a circle, say P1P_1. Then, you select another uniformly random point on the circumference, P2P_2, and draw a line segment between P1P_1 and P2P_2. You then continue to select uniformly random points on the circumference of the circle, say P3,,PnP_3, \dots, P_n, and draw a line segment between PiP_i and Pi+1P_{i+1} for each 1in11 \leq i \leq n-1. Lastly, you draw a line segment from PnP_n back to P1P_1. Find the expected number of intersections between line segments on the interior of the circle as a function of nn. Evaluate this for n=12n = 12.

解析

把这看作:在凸位置的 nn 个点上,随机选择一个哈密顿环(按抽样顺序给出)。

一次内部交点由 4 个顶点决定:对任意 4 点,只有其两条对角线会相交。设该 4 点对应对角线为两条固定不相交边 e1,e2e_1,e_2(在图上端点不重合)。

随机哈密顿环包含两条给定不相交边的概率为

4(n1)(n2).\frac{4}{(n-1)(n-2)}.

(计数:总哈密顿环数 (n1)!/2(n-1)!/2;同时包含两边的环数 2(n3)!2(n-3)!。)

故交点期望为

(n4)4(n1)(n2)=n(n3)6.\binom{n}{4}\cdot\frac{4}{(n-1)(n-2)}=\frac{n(n-3)}{6}.

n=12n=12

E[#intersections]=1296=18.\mathbb{E}[\#\text{intersections}]=\frac{12\cdot 9}{6}=18.

答案:函数为 n(n3)6\boxed{\frac{n(n-3)}{6}},在 n=12n=12 时为 18\boxed{18}