HMMT 二月 2018 · 几何 · 第 9 题
HMMT February 2018 — Geometry — Problem 9
题目详情
- Po picks 100 points P , P , . . . , P on a circle independently and uniformly at random. He then draws 1 2 100 the line segments connecting P P , P P , . . . , P P . When all of the line segments are drawn, the 1 2 2 3 100 1 circle is divided into a number of regions. Find the expected number of regions that have all sides bounded by straight lines.
解析
- Po picks 100 points P , P , . . . , P on a circle independently and uniformly at random. He then draws 1 2 100 the line segments connecting P P , P P , . . . , P P . When all of the line segments are drawn, the 1 2 2 3 100 1 circle is divided into a number of regions. Find the expected number of regions that have all sides bounded by straight lines. Proposed by: Allen Liu 4853 Answer: 3 If the 100 segments do not intersect on the interior, then the circle will be cut into 101 regions. By Euler’s formula, each additional intersection cuts two edges into two each, and adds one more vertex, so since V − E + F is constant, there will be one more region as well. It then suffices to compute the expected number of intersections, where two segments that share a vertex are not counted as intersections. We use linearity of expectation to compute this value. It suffices to compute the expected number of segments that each segment intersects. Consider one such segment P P . It cannot possibly intersect 1 2 a segment that shares an endpoint, so that leaves 97 possible other segments. Again, by linearity of expection, it suffices to compute the probability that P P intersects P P . However, since each of 1 2 i i +1 the points was chosen uniformly at random, this is equal to the probability that AC intersects BD , where A, B, C, D are chosen uniformly at random from the circle. Since this probability is 1 / 3, each 97 segment intersects with segments on average. 3 97 4850 Now, we can sum over all segments and divide by two to get (100 · ) / 2 = intersections, since 3 3 each intersection is counted twice. Accounting for the fact that there are 101 regions to begin with, 4850 4853 and exactly 100 of them have an arc on the boundary, we get + 101 − 100 = as the answer. 3 3